Misterious Buttons

Mysterious button

You decide to earn coins in a dungeon on the outskirts of town. There are N rooms in this dungeon, numbered from 1 to N. In addition, there are mysterious buttons called "coin button", "escape button", and "warp button" in the dungeon. The details of each button are as follows.

• There is exactly one coin button in each room. You can press the coin button as many times as you like, and you will get one coin each time.
• There is exactly one escape button in each room. When you press the escape button, you immediately escape from the dungeon and end this adventure.
• There are a total of M warp buttons. The i-th warp button is in room ai, and when you press it, you warp into room bi and you get ci coins. However, ai <bi and 1 ≤ ci ≤ 3 are satisfied. There may be multiple warp buttons in one room, or there may be rooms without warp buttons at all.

The room cannot be moved by any method other than pressing a button, and multiple buttons cannot be pressed at the same time. Also, both buttons are distinguishable from each other.

You have adventured in this dungeon Q times. If you remember correctly, the jth adventure should have started in room 1, and finally pressed the escape button in room dj, and the total number of coins earned should have been exactly ej. Find out how many such buttons are pressed for each of the Q adventures. The answer can be large, so find the remainder divided by 109 + 7, or 1000000007.

However, the two different "button pressing methods" mean that the total number of times the button is pressed is different, or that there is an integer k and the button pressed the kth time is different.

Perhaps your memory is wrong and there is no way to press such a button. In that case, output 0.

Input

The input consists of multiple datasets. Each dataset is represented in the following format.

N M a1 b1 c1 a2 b2 c2 ... aM bM cM Q d1 e1 d2 e2 ... dQ eQ

The first line of the dataset is given the integer N, which represents the number of rooms, and the integer M, which represents the number of warp buttons, and satisfies 1 ≤ N, M ≤ 20000. The following M line gives the warp button information. The i-th line of the M line is given the room number ai where the i-th warp button exists, the room number bi of the warp destination, and the number of coins that can be obtained ci, and 1 ≤ ai <bi ≤ N and 1 ≤ Satisfy ci ≤ 3. The second line of M + is given the integer Q, which represents the number of adventures, and satisfies 1 ≤ Q ≤ 2 000. The following Q line gives you information about the adventure in your memory. The jth line of the Q line is given the room number dj you pressed the escape button in the jth adventure and the number of coins earned ej, satisfying 1 ≤ dj ≤ N and 1 ≤ ej ≤ 109.

The end of the input is represented by a line consisting of only two zeros. The total number of all datasets does not exceed 50.

Output

The output for each dataset consists of Q lines. On the jth line, start from room 1 and finally press the escape button in room dj, and divide the total number of button presses such that the total number of coins earned is exactly ej by 109 + 7. Output the remainder.

Sample Input

4 9 1 2 1 1 2 2 1 3 1 1 3 2 1 3 3 2 3 1 2 3 2 1 4 1 3 4 2 8 1 5 twenty five 3 5 4 5 1 1234567 2 1234567 3 1234567 4 1234567 4 8 1 2 1 1 2 1 one two Three 3 4 3 1 4 2 2 4 1 2 4 3 2 4 3 8 13 2 6 3 8 4 12 1 31415926 2 53589793 3 23846 4 26433832 0 0

Output for the Sample Input

1 9 37 twenty one 1 2469133 307629943 60012504 1 16 0 424 1 160769377 0 43581113

Example

Input

4 9 1 2 1 1 2 2 1 3 1 1 3 2 1 3 3 2 3 1 2 3 2 1 4 1 3 4 2 8 1 5 2 5 3 5 4 5 1 1234567 2 1234567 3 1234567 4 1234567 4 8 1 2 1 1 2 1 1 2 3 3 4 3 1 4 2 2 4 1 2 4 3 2 4 3 8 1 3 2 6 3 8 4 12 1 31415926 2 53589793 3 23846 4 26433832 0 0

Output

1 9 37 21 1 2469133 307629943 60012504 1 16 0 424 1 160769377 0 43581113

inputFormat

outputFormat

output 0.

Input

The input consists of multiple datasets. Each dataset is represented in the following format.

N M a1 b1 c1 a2 b2 c2 ... aM bM cM Q d1 e1 d2 e2 ... dQ eQ

The first line of the dataset is given the integer N, which represents the number of rooms, and the integer M, which represents the number of warp buttons, and satisfies 1 ≤ N, M ≤ 20000. The following M line gives the warp button information. The i-th line of the M line is given the room number ai where the i-th warp button exists, the room number bi of the warp destination, and the number of coins that can be obtained ci, and 1 ≤ ai <bi ≤ N and 1 ≤ Satisfy ci ≤ 3. The second line of M + is given the integer Q, which represents the number of adventures, and satisfies 1 ≤ Q ≤ 2 000. The following Q line gives you information about the adventure in your memory. The jth line of the Q line is given the room number dj you pressed the escape button in the jth adventure and the number of coins earned ej, satisfying 1 ≤ dj ≤ N and 1 ≤ ej ≤ 109.

The end of the input is represented by a line consisting of only two zeros. The total number of all datasets does not exceed 50.

Output

The output for each dataset consists of Q lines. On the jth line, start from room 1 and finally press the escape button in room dj, and divide the total number of button presses such that the total number of coins earned is exactly ej by 109 + 7. Output the remainder.

Sample Input

4 9 1 2 1 1 2 2 1 3 1 1 3 2 1 3 3 2 3 1 2 3 2 1 4 1 3 4 2 8 1 5 twenty five 3 5 4 5 1 1234567 2 1234567 3 1234567 4 1234567 4 8 1 2 1 1 2 1 one two Three 3 4 3 1 4 2 2 4 1 2 4 3 2 4 3 8 13 2 6 3 8 4 12 1 31415926 2 53589793 3 23846 4 26433832 0 0

Output for the Sample Input

1 9 37 twenty one 1 2469133 307629943 60012504 1 16 0 424 1 160769377 0 43581113

Example

Input

4 9 1 2 1 1 2 2 1 3 1 1 3 2 1 3 3 2 3 1 2 3 2 1 4 1 3 4 2 8 1 5 2 5 3 5 4 5 1 1234567 2 1234567 3 1234567 4 1234567 4 8 1 2 1 1 2 1 1 2 3 3 4 3 1 4 2 2 4 1 2 4 3 2 4 3 8 1 3 2 6 3 8 4 12 1 31415926 2 53589793 3 23846 4 26433832 0 0

Output

1 9 37 21 1 2469133 307629943 60012504 1 16 0 424 1 160769377 0 43581113

样例

4 9
1 2 1
1 2 2
1 3 1
1 3 2
1 3 3
2 3 1
2 3 2
1 4 1
3 4 2
8
1 5
2 5
3 5
4 5
1 1234567
2 1234567
3 1234567
4 1234567
4 8
1 2 1
1 2 1
1 2 3
3 4 3
1 4 2
2 4 1
2 4 3
2 4 3
8
1 3
2 6
3 8
4 12
1 31415926
2 53589793
3 23846
4 26433832
0 0

1
9
37
21
1
2469133
307629943
60012504
1
16
0
424
1
160769377
0
43581113

</p>