CF1707F Bugaboo

A transformation of an array of positive integers $ a_1,a_2,\dots,a_n $ is defined by replacing $ a $ with the array $ b_1,b_2,\dots,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,\dots,c_n $ ( $ 0 \le c_i \le 2^w-1 $ ) to be bugaboo if and only if there exists an array $ a_1,a_2,\dots,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\le n\le 10^7 $ , $ 0\le m\le \min(n, 10^5) $ , $ 1\le t\le 10^9 $ , $ 1\le w\le 30 $ ). The $ i $ -th line of the following $ m $ lines contains two integers $ d_i $ and $ e_i $ ( $ 1\le d_i\le n $ , $ 0\le e_i< 2^w $ ). It means the position $ d_i $ of the array $ c $ is given and $ c_{d_i}=e_i $ . It is guaranteed that $ 1\le d_1

The output contains $ q $ lines, denoting your answers.

In the first example, $ n=3 $ , $ t=1 $ , and $ w=1 $ . Let $ ? $ denote a lost position of $ c $ . In the first query, $ c=[1,0,1] $ . The only possible array $ [1,0,1] $ is bugaboo because it can be given by transforming $ [0,1,1] $ once. So the answer is $ 1\bmod 123\,456\,789 = 1 $ . In the second query, $ c=[1,1,1] $ . The only possible array $ [1,1,1] $ is not bugaboo. So the answer is $ 0\bmod 111\,111\,111 = 0 $ . In the third query, $ c=[?,1,1] $ . There are two possible arrays $ [1,1,1] $ and $ [0,1,1] $ . Only $ [0,1,1] $ is bugaboo because it can be given by transforming $ [1,1,0] $ once. So the answer is $ 1\bmod 987\,654\,321=1 $ . In the fourth query, $ c=[?,1,?] $ . There are four possible arrays. $ [0,1,1] $ and $ [1,1,0] $ are bugaboos. $ [1,1,0] $ can be given by performing $ [1,0,1] $ once. So the answer is $ 2\bmod 555\,555\,555=2 $ .