P10308 "Cfz Round 2" Osmanthus

You are given a sequence $a$ of length $n$. We define one operation as: **simultaneously** replace **every** element $a_i$ in the sequence $a$ with $\bigoplus\limits_{j=1}^i a_j$ (i.e., the XOR sum from $a_1$ to $a_i$), where $\bigoplus$ denotes **bitwise XOR**, i.e., `^` in C++. There are $q$ ordered modifications. Each modification gives two integers $x_i, p_i$, meaning to change the value of $a_{x_i}$ to $p_i$. **These modifications are not independent; each modification affects all subsequent modifications.** After each modification, you need to find the **smallest** positive integer $t$ such that after performing the operation $t$ times, the sequence $a$ becomes the same as the sequence $a$ before the operations. It can be proven that such a positive integer $t$ always exists. Since the answer may be very large, you only need to output the result modulo $(10^9+7)$.

The first line contains two integers $n, q$. The second line contains $n$ integers, representing the given sequence $a$. The next $q$ lines each contain two integers $x_i, p_i$, representing one modification.

Output $q$ lines. On the $i$-th line, output one integer: after the $i$-th modification, the smallest positive integer $t$ that satisfies the requirement, modulo $(10^9+7)$.

#### "Sample Explanation #1" After the 1st modification, the sequence $a$ is $\{3,2,0\}$. After performing the operation 1 time, the sequence $a$ becomes $\{3,1,1\}$. After 2 times, it becomes $\{3,2,3\}$. After 3 times, it becomes $\{3,1,2\}$. After 4 times, it becomes $\{3,2,0\}$. Therefore, the smallest required positive integer $t$ is $4$. #### Constraints For all data, $1 \le n,q \le 3\times10^5$, $0 \le a_i,p_i \le 10^9$, $1 \le x_i \le n$. **Only if you pass all test points of this problem can you get the score for this problem.** Translated by ChatGPT 5