406205: GYM102309 G Game of Orz Pandas

Orz Pandas have invented an interesting game. Now Masters wang9897 and qkoqhh are playing this game.

This game is played in $$$n$$$ rooms. In the beginning of the game qkoqhh would create a pile containing $$$x$$$ stones using a magic. Then wang9897 will choose two numbers $$$l$$$, $$$r$$$ ($$$1 \leq l \leq r \leq n$$$). There are many piles of stones in each room. The Orz Pandas have a magic to duplicate a pile so there may be many piles with the same size. qkoqhh can choose exactly $$$1$$$ or $$$0$$$ piles from each room between the $$$l$$$-th one and the $$$r$$$-th one (inclusively).

After that wang9897 and qkoqhh will play Nim game on all the piles created or chosen by qkoqhh. wang9897 will take the first move.

Now qkoqhh knows the value of $$$n$$$ and $$$x$$$. For each pile in one of the rooms, he knows its size and the room where it is. While wang9897 is chosing $$$l$$$ and $$$r$$$, qkoqhh will ask the Orz Pandas $$$Q$$$ questions. The $$$i$$$-th question is:

"How many ways can I choose the piles in the rooms to win the game, if wang9897 chooses the number $$$l_i$$$ and $$$r_i$$$?"

To solve this problem and get a balloon, you have to answer all the questions for the Orz Pandas. Note that even if two piles have the same number of stones, they should be considered as two different piles.

In case you don't know Nim game, its rule is given:

• In each move, the player taking the move must choose a non-empty pile and remove some (at least one) stones from it. It's allowed to remove all the stones in a pile.
• The two players take turns to move. wang9897 takes the first move, and qkoqhh takes the second move, etc.
• The player who can not take any move in his turn loses the game.

There are multiple test cases. Please process until EOF.

For each test case, the first line contains two integers $$$n$$$ and $$$x$$$.

The second line contains an integer $$$m$$$.

Each of the next $$$m$$$ lines contains three integers $$$p_i$$$, $$$q_i$$$, $$$c_i$$$, representing there are $$$c_i$$$ piles, each contains $$$p_i$$$ stones, in the $$$q_i$$$-th room.

The next line contains an integer $$$Q$$$. The $$$i$$$-th of the next $$$Q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$.

It's guaranteed that $$$1 \leq l_i, r_i, q_i \leq n \leq 500$$$, $$$1 \leq m \leq 10000$$$, $$$0 \leq p_i, x \leq 500$$$, $$$1 \leq c_i \leq 10000$$$, and $$$1 \leq Q \leq \binom{n+1}{2}$$$.

For each question of qkoqhh, output one line containing the answer modulo $$$10007$$$.

3 1
3
1 1 2
2 2 1
2 3 1
3
1 1
1 2
1 3
3 0
3
1 1 1
1 1 1
2 2 2
1
1 3

2
2
4
1

In the first sample, for the first and second question, qkoqhh can choose any one pile from the first room. For the third question, he can also choose one pile from the first room, then choose all piles in the second and the third room.

In the second sample, qkoqhh should not choose any pile from the rooms.