|
H |
Stick
Makes Gold Input: Standard Input Output: Standard Output |
In a village far far away, there lived a cowboy named 'Rakhal Balok'. He used to spend most of his time with his cows. Though he was poor, he was happy with his life, cause his life was simple and trouble-less. Each day, after leaving the cows in the field, he used to wander around. The days were going fine except one day he found a cave in a jungle not too far away from the field. As he was curious and the cave looked so interesting, he had no option but to go inside it.
After entering the cave, he found that the cave was way too long with no branches. And after reaching the end of the cave he found another jungle. Alas! It's nothing but a big disappointment. But wait! There is something fishy. He saw that the cave was long, he passed the cave but the time spent was really low. He saw the sun and he became sure about that. So, there was something in the cave that he missed. So, he began to walk into the cave again. In the last time he wanted to check for branches, but this time he wanted to see the details of the cave.
Soon, he found some sticks lying in the ground. And he could see that the number of sticks was huge, but one thing was common - they were placed in a straight line. That means he could touch one end of a stick, not the other end. To touch the other end he had to walk to reach the other end. Not only this, he found that the sticks were magical. When he touched a stick he got some gold coins. After collecting some gold coins, he found the behavior of the sticks. Here we list his discoveries while he was returning back.
"The length of the sticks are integers and each unit part of a stick is numbered as 1, 2, 3 … Suppose starting and ending point of a stick is 3 and 5 respectively. Then the part (3 4) is denoted as the first part and (4 5) is numbered as the second part. There are three types of sticks
1) Ekka: If the length of the stick is n and anyone touches the ith part of the stick, it will produce i gold coins. For example, if a stick is of length 5, then there are 5 parts of the stick. If anyone touches the first part, he will get 1 gold coin, if anyone touches the 4th part he will get 4 gold coins.
2) Dokka: If the length of the stick is n and anyone touches the ith part of the stick, it will produce i2 gold coins. For example, if a stick is of length 5 and anyone touches the 2nd part, he will get 4 gold coins, if anyone touches the 4th part he will get 16 gold coins.
3) Trikka: If the length of the stick is n and anyone touches the ith part of the stick, it will produce i3 gold coins. For example, if a stick is of length 5 and anyone touches the 2nd part, he will get 8 gold coins, if anyone touches the 4th part he will get 64 gold coins.
The length of the cave is N. What will be the number of coins if I reach the end of the cave? Since the time is not an issue here, I will touch every part of every stick."
Now you are given the information about the sticks and the cave. You have to find the total number of gold coins found by our cowboy. You can assume that the cowboy started his journey (returning back) from the position 0 and he will get out if he reaches N. And all the other information will be given based on his position. All the sticks will be strictly inside the cave.
Input
The first line of the input file will contain T (<= 20), denoting the number of test cases.
The first line of each case will contain two integers, N ( 1 <= N <= 1000000 ) denoting the length of the cave and M ( 1 <= M <= 100000 ) denoting the number of sticks. Each of the next M lines will contain three integers t ai bi ( 1 <= t <= 3, 0 <= ai < bi < N ), where t is the type, ai is the start point and bi is the end point of the stick. The next line will contain an integer Q ( <= 100000 ) denoting the number of queries. The next line contains Q sorted integers separated by spaces, denoting the position of our cowboy.
Output
For each case of input print the case number in a single line. Then There should be Q lines, containing the number of total gold coins collected by our cowboy in the given position. Check the samples for more details. The result can be big, so, print the result modulo 264.
Note: Large input output file, use faster i/o functions, e.g. scanf, printf.
Sample
Input Output
for Sample Input
110 3 1 2 42 3 73 4 652 3 4 5 10 |
Case 1: |
Problem setter: Jane Alam Jan, Special Thanks: Md. Arifuzzaman Arif