题号：NC17447
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
There are n trains running between Kanto and Johto region. Assuming the railway is a number line, the i-th train travels from coordinate li to coordinate ri (both inclusive).
One day, m Team Rocket members invaded the railway system successfully. The i-th Team Rocket member was going to destroy the transportation hub with coordinate xi. Once a transportation hub within the driving range of a train is destroyed, the train's itinerary will be canceled immediately.
Giovanni wants to know how many train trips will be firstly canceled after each attack.
After all the attacks finished, for each train Giovanni needs to know that in which attack its itinerary was firstly canceled, or it was unaffected at all.
One day, m Team Rocket members invaded the railway system successfully. The i-th Team Rocket member was going to destroy the transportation hub with coordinate xi. Once a transportation hub within the driving range of a train is destroyed, the train's itinerary will be canceled immediately.
Giovanni wants to know how many train trips will be firstly canceled after each attack.
After all the attacks finished, for each train Giovanni needs to know that in which attack its itinerary was firstly canceled, or it was unaffected at all.
输入描述:
The input starts with one line containing exactly one integer T, which is the number of test cases.
For each test case, the first line contains two integers n and m, indicating the number of trains and the number of Team Rocket members.
Each of the next n lines contains 2 integers li and ri, indicating the driving range of the i-th train.
Each of the next m lines contains exactly one integer yi., where xi is the transportation hub that Team Rocket members would destroy in the i-th attack, resi-1 is the product of the indexes of trips cancelled by the (i-1)-th attack and
means exclusive or.
If no such trip exists, resi-1 is considered to be 0.
- 1 ≤ T ≤ 5.
- 1 ≤ n,m ≤ 2 x 105.
- -109 ≤ li ≤ ri ≤ 109.
- -109 ≤ xi ≤ 109.
输出描述:
For each test case, output one line "Case #x:" first, where x is the test case number (starting from 1).
Then output m lines, each line of which contains exactly one integer, indicating the number of train trips firstly canceled after the i-th attack.
Finally output one line, containing n integers, where the i-th integer is the time when the i-th train trip is firstly canceled or 0 if it is not affected.