Bobo made a very long sequence of numbers (a₁, a₂, . . . , a_n) in ICPCCamp where a_i = f(i) and
.
Now he wants to ask q questions where the i-th question is to compute the sum of a_li , a_li+1, . . . , a_ri . Unfortunately,
the only tool which Bobo can utilize is an old broken 4-bit counter. While trying to answer the i-th
question, Bobo will set the counter to 0, and add numbers to the counter in the order of a_li , a_li+1, . . . , a_ri .
As the counter is broken, adding the number a to a counter holding value x yields [(x⊕w_i) + a] mod 16.
Note that “⊕” stands for bitwise exclusive or (XOR).
Bobo would like to know the final result.
Special Note: The time limit is tight so that some optimization might be necessary. Try to solve the problem
as late as possible.

The input contains zero or more test cases and is terminated by end-of-file. For each test case:
The first line contains five integers n, m, A, B, q. The i-th of the following q lines contains three integers l_i,
l_i and w_i.
• 1 ≤ n ≤ 10⁸
• 2 ≤ m ≤ 10⁵
• 0 ≤ A,B,w_i < 16
• 1 ≤ q ≤ 13
• 1 ≤ l_i ≤ r_i ≤ n
• The number of test cases does not exceed 10.

5 2 1 1 2
1 4 0
2 5 1

2
15

2017年四川省赛