该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 5: Déjà Vu!

Although he had already reached the Steins Gate, Rintaro Okabe, burdened by the heavy load of traversing various world lines, uncontrollably shifted into the CS100 world. "It seems this day has come after all," Rintaro Okabe tried to clear his mind. Earlier, Kurisu Makise had discussed with him the possibility of shifting into the CS100 world and had devised a strategy to return to the Steins Gate.

According to Kurisu Makise's hypothesis, the CS100 world contains a total of $n$ world lines, numbered from $1$ to $n$. Kurisu Makise thus created a monitoring machine that can observe the layout of the world lines and the $32$-bit singularity value $s_i$ of each world line. Each world line also has an outgoing edge $p_i$, this edge would cause effect to connecting world line. Initially, $p_i=i$.

At time $j$, an event $(x_j, y_j)$ will occur, indicating that the $x_j$-th world line will change its edge $p_{x_j}=y_j$ (note that $y_j$ may be equal to $x_j$). Moreover, affected by this, the singularity values of the world lines reachable from the $x_j$-th world line will change. Assuming the singularity value of the $x_j$-th world line is $s$, the singularity value of the world line $p_{x_j}$, which is reached after passing one outgoing edge from $x_j$, will be XORed with the result of $s$ cyclically shifted left once. And the singularity value of the world line $p_{p_{x_j}}$, which is reached after passing twice through outgoing edge from $x_j$, will be XORed with the result of $s$ cyclically shifted left twice. In general, the singularity value of the world line reached after passing $i$ outgoing edges will be XORed with the result of $s$ cyclically shifted left $i$ times. This process will terminate either after encountering a world line whose singularity value has been modified by this event or after shifting into world line itself (this event would not change singularity value $s_x$).

A cyclic shift left is defined as shifting a binary number to the left once, with the highest bit of the binary number moving to the lowest bit, and the other bits moving one place to the left. For example, if $s=\underbrace{(10101...0110)_2}_{\text{32 bits in total}}$, the result of shifting $s$ once is $\underbrace{(01010...1101)_2}_{\text{32 bits in total}}$, and the result of shifting $s$ twice is $\underbrace{(10100...1010)_2}_{\text{32 bits in total}}$.

Rintaro Okabe needs to reach the world line with the smallest singularity value to trigger the Steins Gate. Now, Rintaro Okabe has foreseen the occurrence of the next $Q$ events through the machine and has already calculated the final destination.

Input Format

The first line contains two integers $n, Q (1 \le n\le 1000, 1\le Q \le 4000)$, separated by a space, indicating there are $n$ world lines and $Q$ events occurring in sequence.

The second line contains $n$ integers $s_i (0 \le s_i < 2^{32})$, which is a $32$-bit unsigned integer, representing the initial singularity values of the $n$ world lines.

The next $Q$ lines each contain two integers $x_j, y_j$, $(1 \le x_j, y_j \le n)$, indicating the changes in the world lines.

Output Format

Output two integers $x, s_x$ on two lines, representing the world line $x$ with the smallest final singularity value and its singularity value $s_x$. If there are multiple world lines with the smallest singularity value, output the one with the smallest number.

6 5
1 2 3 4 5 6
1 1
2 5
3 5
6 2
2 1

3
3

Sample 1 explaination:

We use $\oplus$ to denote bitwise xor, $<<$ to denote cyclic left shift.

After $(1,1)$, nothing change.

After $(2,5)$, $p_2=5$, $s_5 = 5 \oplus (2<<1) = 1$

After $(3,5)$, $p_3=5$, $s_5=1\oplus (3<<1) = 7$

After $(6,2)$, $p_6=2$, $s_2 = 2\oplus (6<<1) = 14, s_5=7\oplus (6<<2) = 31$

After $(2,1)$, $p_2=1$, $s_1=1\oplus (14<<1) = 29$

10 0
3 2 10 3 1 9 1 2 4 22

5
1

3 5
3 2 1
1 2
2 3
3 1
3 3
1 3

1
17

EL PSY KONGROO