Meteors

The Byteotian Interstellar Union (BIU) has recently discovered a new planet near a distant galaxy. Meteor showers fall on it so often that it is unfit for human habitation, but it turns out to be an excellent place to study those very showers.

The BIU member states have already built a space station near the planet. The station's purpose is to collect samples of the meteorites left behind by the showers. The planet's orbit is a circle divided into M sectors numbered 1 through M. Because the orbit is circular, sector 1 and sector M are adjacent. The N member states divide the sectors among themselves.

Each member state has set a target number of meteorite samples it wants to collect. Given a forecast of the upcoming meteor showers, determine when each state can meet its target.

The first line contains two integers N and M ($1 \le N, M \le 300{,}000$): N is the number of member states and M is the number of orbital sectors.

The second line contains M integers $o_1, o_2, \dots, o_M$ ($1 \le o_i \le N$), where $o_i$ is the number of the member state that owns sector i.

The third line contains N integers $p_1, p_2, \dots, p_N$ ($1 \le p_j \le 10^9$), where $p_j$ is the number of meteorite samples that member state j aims to collect.

The fourth line contains an integer Q ($1 \le Q \le 300{,}000$), the number of forecast meteor showers.

Each of the next Q lines describes one shower in chronological order. The u-th of these lines contains three integers $l_u$, $r_u$, and $a_u$ ($1 \le l_u, r_u \le M$, $1 \le a_u \le 10^9$). If $l_u \le r_u$, then $a_u$ meteorites fall on each of sectors $l_u, l_u+1, \dots, r_u$; if $l_u > r_u$, then $a_u$ meteorites fall on each of sectors $l_u, l_u+1, \dots, M, 1, \dots, r_u$. This shower happens on day u, counting from the start of the forecast.

Print N lines. On the j-th line print $w_j$, the minimum number of days after which member state j meets its target, in order of state number. By the end of day $w_j$, the total number of meteorite samples that have fallen on the sectors owned by state j must be at least $p_j$. If a state cannot reach its target within the Q forecast days, print NIE (Polish for "no") on its line instead.