Circuit 101

Calculating equivalent resistance is the basic knowledge for solving any circuit related problems. Solving these problems always involve some resistors with fixed resistance. But in reality, that's never possible due to thermal and manufacturing issues. Thus any resistor is provided with a tolerance level to account for the manufacturing issues. In other words, every resistor has a certified lower and upper bound of the resistance at standard temperature. Now, you are given n resistors with separate lower and upper bounds. After connecting them in series, what would the probability of getting equivalent resistance equal to x? For simplicity, we will consider that resistance can only be positive integers and probability of getting any value of resistance within the bound is equal.

Input

First line of the input contains two integers n (0 < n ≤ 100) and q (0 < q ≤ 105) where n represents the number of resistors and q for number of queries. Each of the next n line contains two integers l and r (0 < l ≤ r ≤ 50000) representing lower and upper bound of the resistors. Next q line each contains an integer x (0 < x ≤ 105), the desired value of equivalent resistance.

Output

For each query find P(x), probability of getting x as equivalent resistance. P(x) can be written as a/b where a and b are integers. Print P(x) modulo 1000003.

Sample

Input	Output
2 3 1 3 1 2 2 3 5	833336 666669 833336

Formula to calculate equivalent resistance of n resistors connected in series,
Req = R1 + R2 + R3 .... + Rn.