import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Scanner; public class Solution { static long root; static int mod = 1_000_000_007; public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int a = in.nextInt(); int b = in.nextInt(); int q = in.nextInt(); int[] c = new int[n]; root = (((-1L*b*inverse(a, mod))%mod) +mod)%mod; List values = new ArrayList(); for(int c_i=0; c_i < n; c_i++){ c[c_i] = in.nextInt(); values.add((c[c_i]*power(root, c_i, mod))%mod); } SumSegmentTree tree = new SumSegmentTree(values); for(int a0 = 0; a0 < q; a0++){ int queryType = in.nextInt(); int first = in.nextInt(); int second = in.nextInt(); if(queryType==1){ tree.updateIndex(first, (second*power(root, first, mod))%mod); } else { System.out.println(tree.intervalValue(first, second)*inverse(power(root,first,mod),mod)%mod==0 ? "Yes" : "No"); } } } private static long atRoot(int from, int to, int[] coef){ long atRoot = 0; for(int i=from; i<=to; i++) { atRoot = (atRoot + coef[i]*power(root, i-from, mod))%mod; } return atRoot; } public static long power(long base, long exp, int mod){ if(exp==0) return 1; long result = 1; while(exp > 0){ if(exp%2==0) { base = (base*base)%mod; exp /= 2; } else { exp--; result = (result*base)%mod; } } return result; } /** * Return multiplicative inverse of number in Zp. * NUMBER MUST NOT BE ZERO. */ public static long inverse(long number, int prime){ return power(number, prime-2, prime); } } abstract class SegmentTree { private List> nodes; /** * maps original index to nodeIndex in nodes */ private Map map; public SegmentTree(List data) { initialize(data); } private void initialize(List values){ map = new HashMap(values.size()); int nodesSize = 4 * values.size() + 1; nodes = new ArrayList>(nodesSize); for (int i = 0; i < nodesSize; i++){ nodes.add(null); } createTree(values, 0, values.size() - 1, 0); } private void createTree(List values, int left, int right, int nodeIndex) { SegmentTreeNode node = new SegmentTreeNode(left, right); nodes.set(nodeIndex, node); if (left == right) { node.value = values.get(left); map.put(left, nodeIndex); } else { int mid = (left + right) / 2; createTree(values, left, mid, 2 * nodeIndex + 1); createTree(values, mid + 1, right, 2 * nodeIndex + 2); node.value = join(node.value, valueAtNode(2 * nodeIndex + 1), valueAtNode(2 * nodeIndex + 2)); } } /** * Changes value at index of original field(array) to value. */ public void updateIndex(int index, T value) { int nodeIndex = map.get(index); nodes.get(nodeIndex).value = value; if (nodeIndex != 0) { recalculateNodeValue((nodeIndex - 1) / 2); } } // TODO zmenit podla potrieb lazy update /** * Recalculate value at given nodeIndex base on two childs. DO NOT USE FOR LEAF */ private void recalculateNodeValue(int nodeIndex) { SegmentTreeNode node = nodes.get(nodeIndex); node.value = join(node.value, valueAtNode(2 * nodeIndex + 1), valueAtNode(2 * nodeIndex + 2)); // if it is not root, update parent if (nodeIndex != 0) { recalculateNodeValue((nodeIndex - 1) / 2); } } private T valueAtNode(int nodeIndex) { return nodes.get(nodeIndex).value; } /** * Returns value of interval . */ public T intervalValue(int left, int right) { return intervalValue(left, right, 0); } // TODO prerobit na lazy // TODO zda sa mi to prilis komplikovane private T intervalValue(int left, int right, int nodeIndex) { SegmentTreeNode node = nodes.get(nodeIndex); T toReturn = null;; // if whole node interval is under required interval, return it if (left <= node.left && node.right <= right){ toReturn = node.value; } else { SegmentTreeNode leftChild = nodes.get(2 * nodeIndex + 1); SegmentTreeNode rightChild = nodes.get(2 * nodeIndex + 2); if (overlap(left, right, leftChild.left, leftChild.right) && overlap(left, right, rightChild.left, rightChild.right)) { toReturn = join(toReturn, intervalValue(left, right, 2 * nodeIndex + 1), intervalValue(left, right, 2 * nodeIndex + 2)); } else if (overlap(left, right, leftChild.left, leftChild.right)) { toReturn = intervalValue(left, right, 2 * nodeIndex + 1); } else { toReturn = intervalValue(left, right, 2 * nodeIndex + 2); } } return toReturn; } private boolean overlap(int left1, int right1, int left2, int right2) { return left1 <= right2 && left2 <= right1; } /** * Apply join operation on values, e.g. sum, max, product,... * Result can input as null. * It is possible to return result of join or * modify result object. */ protected abstract T join(T result, T value1, T value2); @Override public String toString(){ StringBuilder sb = new StringBuilder(); for (SegmentTreeNode segmentTreeNode : nodes) { if(segmentTreeNode!=null){ sb.append(segmentTreeNode+"\n"); } } return sb.toString(); } } class SegmentTreeNode { int left; int right; T value; //if updateValue is not null, update is needed T updateValue; public SegmentTreeNode(int left, int right) { this.left = left; this.right = right; } @Override public String toString() { return "(" + left + "," + right + ") -> " + value; } } class SumSegmentTree extends SegmentTree { public SumSegmentTree(List data) { super(data); } @Override protected Long join(Long result, Long value1, Long value2) { return (value1 + value2)%1000000007; } } class MaxSegmentTree extends SegmentTree { public MaxSegmentTree(List data) { super(data); } @Override protected Integer join(Integer result, Integer value1, Integer value2) { return Math.max(value1, value2); } } class MinSegmentTree extends SegmentTree { public MinSegmentTree(List data) { super(data); } @Override protected Integer join(Integer result, Integer value1, Integer value2) { return Math.min(value1, value2); } }