Xiao Po is building a validation framework for his current project. He is now stuck with this problem:
There are N ranges of integers. A range of integers is defined by two integers Low and High where 1 <= Low <= High <= 10^9. Then there are 1 <= Q <= 10^5 queries. Each query consists of one single integer between [1, 10^9]. You have to find the number of ranges this
query integer is valid for.
A query integer is valid for a range if it is a prefix of some number in the given range [Low, High], including Low and High, and invalid otherwise.
Input
First line of input is an integer T (1 <= T <= 5) that denotes number of test cases. Each of the next T test cases starts with two integers N and Q. Then the next N (1 <= N <= 20000) lines each contain two integers Low and High. Each of the next Q lines contain one integer.
Output
For each query integer print the number of ranges this integer is valid for.
Sample
| Input | Output |
|---|---|
1 1 6 310 320 3 31 32 41 317 3174 | 1 1 1 0 1 0 |
- 310 begins with 3, therefore 3 is valid
- 315 begins with 31, therefore 31 is valid
- 320 begins with 32, therefore 32 is valid
- No integers between 310 to 320 begins with 41, therefore invalid
- 317 begins with 317, therefore 317 is valid
- No integers between 310 to 320 begins with 3174, therefore invalid.
This problem was authored for Inter Department Programming Contest 2016 at Jahangirnagar University and is being hosted on Toph per author's request.
