A. Arrival Signs
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
SMRT Information Sign

The MRT Information System tells commuters when the next train will arrive. However, Bob is worried that displaying the next train's arrival time too directly may encourage commuters to run towards the platform, which is dangerous.

Bob is a software developer working on the next iteration of these information signs with safety in mind.

A day starts at time $$$0$$$. There are $$$n$$$ platforms. For platform $$$j$$$, trains arrive every $$$t_j$$$ minutes; that is, trains serving platform $$$j$$$ arrive at times $$$$$$0, t_j, 2t_j, 3t_j, \cdots$$$$$$ The station also has $$$m$$$ information signs. A commuter is estimated to take $$$d_{i,j}$$$ minutes to walk from sign $$$i$$$ to platform $$$j$$$.

Suppose a commuter leaves sign $$$i$$$ at time $$$x$$$ and walks to platform $$$j$$$. The sign displays the number of minutes from time $$$x$$$ until the earliest train they can catch. Formally, a commuter who starts walking from sign $$$i$$$ reaches platform $$$j$$$ at time $$$$$$ x + d_{i,j}. $$$$$$ The sign should display the difference between time $$$x$$$ and the arrival time of the earliest train at platform $$$j$$$ that arrives at or after time $$$x + d_{i,j}$$$.

For example, suppose it takes $$$d_{1,1} = 5$$$ minutes to walk from sign $$$1$$$ to platform $$$1$$$, and trains arrive at platform 1 every $$$t_{1} = 6$$$ minutes.

  • At time $$$x = 1$$$, the commuter reaches the platform at time $$$6$$$. The earliest train they can catch arrives at time $$$6$$$, so the sign displays $$$6-1 = 5$$$.
  • At time $$$x = 2$$$, the commuter reaches the platform at time $$$7$$$. The earliest train they can catch arrives at time $$$12$$$, so the sign displays $$$12 - 2 = 10$$$.

Help Bob answer $$$q$$$ queries. For each query $$$(x,i,j)$$$, output the number of minutes displayed on sign $$$i$$$ for platform $$$j$$$ at time $$$x$$$ minutes from the start of the day.

Input
  • The first line contains 2 integers $$$n$$$ and $$$m$$$ ($$$1\leq n, m\leq 100$$$), the number of platforms $$$n$$$ and number of signs $$$m$$$.
  • The second line contains $$$n$$$ integers $$$t_1, t_2, \cdots , t_n$$$ ($$$1\leq t_j \leq 400$$$), the $$$j$$$-th integer denoting the interval between consecutive train arrivals at platform $$$j$$$.
  • The next $$$m$$$ lines contain $$$n$$$ integers each. The $$$i$$$-th line contains the $$$n$$$ integers $$$d_{i,1}, d_{i,2}, \cdots, d_{i, n}$$$ ($$$1 \leq d_{i,j} \leq 400$$$). The $$$j$$$-th integer on the $$$i$$$-th line, $$$d_{i, j}$$$, denotes the time taken to walk from sign $$$i$$$ to platform $$$j$$$.
  • The next line contains a single integer $$$q$$$ ($$$1\leq q\leq 2\times 10^5$$$), the number of queries.
  • The next $$$q$$$ lines each contain three integers $$$x,i,j$$$ ($$$0\leq x \leq 10^3$$$, $$$1\leq i \leq m$$$, $$$1\leq j \leq n$$$), the $$$k$$$-th line containing the values $$$(x,i,j)$$$ for the $$$k$$$-th query.
Output

$$$q$$$ lines, where the $$$i$$$-th line ($$$1\leq i \leq q$$$) contains the answer to the $$$i$$$-th query.

Example
Input
3 2
5 7 1
1 2 3
5 7 10
8
0 1 1
4 1 1
5 1 1
6 1 2
7 2 2
1000 1 3
0 2 1
3 2 1
Output
5
1
5
8
7
3
5
7