A. The Problems Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Eddard and his secret partner are betting on how many problems each contestant will solve in Game Of Coders this year. Eddard knows his secret partner would win the bet if they played fairly, so he decided to get some outside help – your help.

$$$m$$$ contestants have signed up for the contest, and will be given $$$n$$$ problems and $$$t$$$ minutes to solve them. Each contestant $$$i$$$ has a rating $$$r_i$$$, and each problem $$$i$$$ has a difficulty rating $$$d_i$$$, time to solve $$$ts_i$$$, and time to fail $$$tf_i$$$.

Eddard believes this is how each contestant $$$c$$$ performs:

  1. The contestant will pick a problem $$$p$$$ uniformly at random from the problems they haven't picked before.
  2. If their rating is greater than or equal to the problem's difficulty $$$(r_c \ge d_p)$$$, they spend $$$ts_p$$$ minutes solving the problem and succeed. Otherwise, they spend $$$tf_p$$$ minutes trying to solve it before giving up. In both cases, they move on to another problem afterwards.

This process repeats until the time runs out or the contestant has picked every problem once.

For each contestant, print the expected number of solved problems after the contest ends.

Note that if the time runs out at the same minute a contestant finishes solving a problem, the problem is counted as solved.

Input

The first line of input consists of 3 integers $$$n, m, t (1 \le n \le 12, 1 \le m \le 10^5, 1 \le t \le 300)$$$

The next three lines of input describe the problems and consist of $$$n$$$ integers each:

  • $$$d_1, d_2,...,d_n(1 \le d_i \le 9999)$$$ – The difficulties of the problems.
  • $$$ts_1, ts_2,...,ts_n(1 \le ts_i \le 300)$$$ – The time to solve each problem.
  • $$$tf_1, tf_2,...,tf_n(1 \le tf_i \le 300)$$$ – The time to fail at each problem.

The last line consists of $$$m$$$ integers $$$r_1, r_2,...,r_m(1 \le r_i \le 9999)$$$, The rating of each contestant.

Output

print $$$m$$$ integers $$$e_1, e_2,...,e_m$$$, where $$$e_i$$$ is the expected number of problems contestant $$$i$$$ will solve modulo $$$10^9 + 7$$$.

Formally, the expected number can be expressed as an irreducible fraction $$$\frac{x}{y}$$$. You have to print the value of $$$x \cdot y^{-1} \mbox{ mod } 10^9 + 7$$$, where $$$y^{-1}$$$ is an integer such that $$$y \cdot y^{-1} \equiv 1 \mbox{ (mod } 10^9 + 7)$$$.

Examples
Input
1 2 50
1000
50
50
500 1500
Output
0 1
Input
6 8 150
800 1200 1500 1800 2200 2600
2 5 15 25 40 60
10 12 20 40 30 100
900 1300 3000 1260 2500 1750 200 1979
Output
433333337 100000002 6 100000002 716666675 766666674 0 216666671
Note

In the first test Case:

the first contestant has rating $$$500$$$, they pick the only problem with difficulty $$$1000$$$ and spend the $$$50$$$ minutes of the contest trying to solve it but fail, thus solving 0 problems.

The second contestant has rating $$$1500$$$, so they're able to solve it in $$$50$$$ minutes, thus solving 1 problem.

In the second test case, the answer as irreducible fractions is:

$$$ \frac{19}{30}, \frac{13}{10}, \frac{6}{1}, \frac{13}{10}, \frac{199}{60}, \frac{59}{30}, \frac{0}{1}, \frac{169}{60}$$$