Nhân ngày đầu năm mới, thầy giáo của Phát muốn tặng mỗi bạn một điểm số để chọn làm điểm bài kiểm tra 15 phút.

Lớp Phát có ~n~ bạn, được đánh số lần lượt từ ~1~ đến ~n~. Thầy giáo dự định cho điểm như sau:

• Đầu tiên thầy giáo chọn ~4~ số ~m, k, x, q~.

• Gọi điểm bạn thứ ~i~ là ~a_i~.

• ~a_i = x~ nếu ~i = 1~.

• Nếu ~i > 1~ thì ~a_i = (a_{i - 1} \times k) \bmod m~.

• Sau đó lại trừ điểm của tất cả các bạn ~q~ điểm.

Lưu ý điểm có thể âm. (điểm âm là do các bạn kém may mắn :))

Cụ thể hơn, điểm thầy giáo định cho ban đầu được tính bằng mã giả sau:

a[1] = x;
for i from 2 to n:
    a[i] = (a[i - 1] * k) mod m;
for i from 1 to n:
    a[i] = a[i] - q;

Lưu ý: mọi tính toán nên được thực hiện với số nguyên 64-bit.

Sau khi làm các bước như thế thì thầy giáo thấy điểm vẫn còn quá cao nên quyết định thử ~t~ trường hợp.

Mỗi trường hợp thầy chọn ~3~ số ~L, R, D~, điểm số của bạn thứ ~i~ sẽ bị trừ ~D~ nếu ~L \le i \le R~.

Thầy giáo muốn biết trong mỗi trường hợp đó thì số điểm lớn nhất của lớp là bao nhiêu. Bạn hãy giúp thầy giáo nhé!

Input

• Dòng đầu chứa năm số nguyên ~n,m,k,x,q~ ~(1 \le n \le 10^7, 1 \le m, k, x, q \le 10^9)~.
• Dòng thứ hai chứa số nguyên dương ~t~. ~(1 \le t \le 10^5)~
• ~t~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~L_i, R_i, D_i~ cho biết truy vấn thứ ~i~ ~(1 \le L_i \le R_i \le n, 0 \le D_i \le 10^9)~.

Output

• Gồm ~t~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Subtask

• Subtask 1 (30% số điểm): ~n \le 1000~
• Subtask 2 (30% số điểm): ~n \le 10^5~
• Subtask 3 (40% số điểm): Không có ràng buộc gì thêm

Sample Input

5 7 5 1 1
3
1 3 3
1 5 5
4 5 2

Sample Output

5
0
4

Note

• Dãy được sinh ra là ~a=[0, 4, 3, 5, 1 ]~.
• Trong truy vấn ~1~, dãy ~a~ sau khi trừ điểm các bạn có số thứ tự trong đoạn ~[L,R]~ ~D~ điểm là ~a=[-3,1,0,5,1]~.
• Trong truy vấn ~2~, dãy ~a~ sau khi trừ điểm các bạn có số thứ tự trong đoạn ~[L,R]~ ~D~ điểm là ~a=[-5,-1,-2,0,-4]~.
• Trong truy vấn ~3~, dãy ~a~ sau khi trừ điểm các bạn có số thứ tự trong đoạn ~[L,R]~ ~D~ điểm là ~a=[0,4,3,3,-1]~.