B"A transformation of an array of positive integers a_1,a_2, ... ,a_n is defined by replacing a with the array b_1,b_2, ... ,b_n given by b_i=a_i oplus a_{(i bmod n)+1} , where oplus denotes the bitwise XOR operation. You are given integers n , t , and w . We consider an array c_1,c_2, ... ,c_n ( 0 <= c_i <= 2^w-1 ) to be bugaboo if and only if there exists an array a_1,a_2, ... ,a_n such that after transforming a for t times, a becomes c . For example, when n=6 , t=2 , w=2 , then the array [3,2,1,0,2,2] is bugaboo because it can be given by transforming the array [2,3,1,1,0,1] for 2 times: [2,3,1,1,0,1] to [2 oplus 3,3 oplus 1,1 oplus 1,1 oplus 0,0 oplus 1,1 oplus 2]=[1,2,0,1,1,3]; [1,2,0,1,1,3] to [1 oplus 2,2 oplus 0,0 oplus 1,1 oplus 1,1 oplus 3,3 oplus 1]=[3,2,1,0,2,2]. And the array [4,4,4,4,0,0] is not bugaboo because 4 > 2^2 - 1 . The array [2,3,3,3,3,3] is also not bugaboo because it can't be given by transforming one array for 2 times. You are given an array c with some positions lost (only m positions are known at first and the remaining positions are lost). And there are q modifications, where each modification is changing a position of c . A modification can possibly change whether the position is lost or known, and it can possibly redefine a position that is already given. You need to calculate how many possible arrays c (with arbitrary elements on the lost positions) are bugaboos after each modification. Output the i -th answer modulo p_i ( p_i is a given array consisting of q elements). The first line contains four integers n , m , t and w ( 2 <= n <= 10^7 , 0 <= m <= min(n, 10^5) , 1 <= t <= 10^9 , 1 <= w <= 30 ). The i -th line of the following m lines contains two integers d_i$$"...