Дистанционный практикум по программированию

There is a long straight avenue with k traffic lights in the city of NN. All the traffic lights in this avenue are identical, and they have only two states: red (stop) and green (drive). The states change each n seconds for each working traffic light. This interval is the same for all lights. However, the lights may have been initially powered on at different times. The switching times of traffic light number i are determined by the time r_i when it was powered on. After the traffic light is powered on it will remain green for n seconds. Then, at r_i + n, it will turn red, and n more seconds later (at r_i + 2n) it will turn green again, and so on.

There are m cars at the beginning of the avenue. At point in time t₀ = 0 seconds all the cars start moving along the avenue in the same direction with different but constant speeds s₁, s₂, …s_m m/sec. The traffic lights are installed at positions d₁, d₂, …, d_k meters from the beginning of the avenue. A car may pass the traffic light i only if at point in time t, when the car reaches position d_i, traffic light number i is in green state and it is not changing state at the moment t.

r_i + 2xn < t < r_i + (2x+1)n for some non-negative number x.

Write a program that will accept parameters n, m, k, speeds s₁, …, s_m and distances d₁, d₂, …, d_k, and calculate the times r₁, r₂, …, r_k to power on the lights in such a way that all m cars will drive along the avenue without stopping. Note that the traffic lights are designed so that the moments of powering on r₁, r₂, …, r_k have to be expressed as an integer number of seconds. If several solutions exist then any of them will be considered correct.

Limitations

All input and output numbers are integer.

1 <= n <= 10⁶, 1 <= m, k <= 1000;

1 <= s_i, d_i <= 10⁶; i ¹ j : s_i ¹ s_j, d_i ¹ d_j.

0 <= r_i <= 10⁹.

Input

The first line of the input file contains 3 integers n, m, k separated by spaces. The second line consists of m pairwise different integer numbers s₁, s₂, …s_m separated by spaces. These numbers define the speeds of the cars in m/sec. The third line contains k pairwise different integer numbers d₁, d₂, …, d_k separated by spaces. These numbers define the positions of traffic lights (distance from the the beginning of the avenue in m.).

Output

The first line of the input file contains 0 if there is no integer solution, or number k  if such a solution exists. If there is a solution, then the following line contains k integers r₁, r₂, …, r_k delimited by exactly one space.

Samples

Standard input	Standard output
2 2 1 20 11 100	1 4
2 2 1 20 10 100	0