問題文

整数 M, N, A, B, C, D, E, F, G, H が与えられる．整数 p_0, p_1, \ldots, p_{M-1} と q_0, q_1, \ldots, q_{N-1} を以下で定める：

• p_0 = A，p_i = (B p_{i-1} + C) \bmod D   (1 \le i \le M-1)．
• q_0 = E，q_j = (F q_{j-1} + G) \bmod H   (1 \le j \le N-1)．

x の多項式 f(x) = \sum_{i=0}^{M-1} p_i x^i を考える．各 j = 0, 1, \ldots, N-1 に対して r_j = f(q_j) \bmod 3^{19} と定める．

r_0, r_1, \ldots, r_{N-1} の bitwise XOR を求めよ．

ただし，整数 a と正整数 b に対し，a \bmod b で a を b で割った余り (0 以上 b 未満) を表す．

制約

• 1 \le M \le 10^7．
• 1 \le N \le 10^7．
• 0 \le A,B,C < D \le 10^9．
• 0 \le E,F,G < H \le 10^9．

入力例 1

3 4
1 5 7 9
2 6 8 10

出力例 1

428

(p_0, p_1, p_2) = (1, 3, 4), (q_0, q_1, q_2, q_3) = (2, 0, 8, 6), (r_0, r_1, r_2, r_3) = (23, 1, 281, 163) となる．

入力例 2

1000 2000
0 1 1 1000000000
0 1 1 1000000000

出力例 2

663657950