Cho dãy số nguyên ~x_1, x_2, \dots, x_n~. Xét mọi đoạn con liên tiếp độ dài ~k~ từ trái sang phải và tính XOR của từng đoạn.

Trong bài này dữ liệu vào rất lớn và dãy được sinh bằng bộ sinh.

Yêu cầu

Dãy được sinh bởi:

• ~x_1 = x~
• ~x_i = (a \cdot x_{i-1} + b) \bmod c~ với ~i = 2,3,\dots,n~

Với mỗi vị trí ~i~ (từ ~1~ đến ~n-k+1~), đặt:

• ~w_i = x_i \oplus x_{i+1} \oplus \dots \oplus x_{i+k-1}~

Hãy in ra giá trị:

• ~w_1 \oplus w_2 \oplus \dots \oplus w_{n-k+1}~

Trong đó ~\oplus~ là phép XOR bit.

Dữ liệu

• Dòng 1: hai số nguyên ~n~, ~k~.
• Dòng 2: bốn số nguyên ~x~, ~a~, ~b~, ~c~ là tham số bộ sinh.

Kết quả

• In ra một số nguyên: XOR của tất cả các XOR cửa sổ.

Ví dụ

Ví dụ 1

Input

8 5
3 7 1 11

Output

0

Giải thích

Ví dụ 1

Dãy sinh ra là ~[3,0,1,8,2,4,7,6]~.

Các cửa sổ độ dài ~5~ là:

• ~[3,0,1,8,2]~ có XOR ~8~
• ~[0,1,8,2,4]~ có XOR ~15~
• ~[1,8,2,4,7]~ có XOR ~8~
• ~[8,2,4,7,6]~ có XOR ~15~

Do đó đáp án là ~8 \oplus 15 \oplus 8 \oplus 15 = 0~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le k \le n \le 10^7~
• ~0 \le x, a, b \le 10^9~
• ~1 \le c \le 10^9~