Meteor Shower Sampling Deadline

Byteotian Interstellar Union (BIU) has discovered a new planet that, although unsuitable for colonisation, presents a unique opportunity for meteorite research. The BIU Commission has divided the planet's orbit into \( m \) sectors (with sector 1 adjacent to sector \( m \)). In each sector there is a space station belonging to one of the \( n \) member states. Each state has declared a target number of meteor samples they wish to collect.

There are \( q \) predicted meteor shower events. Each event will affect a contiguous block of sectors on the orbit. If the event affects the sectors from \( l \) to \( r \) (inclusive), and \( l \le r \), then every sector \( i \) satisfying \( l \le i \le r \) will collect additional samples. If \( l > r \) the range wraps around so that sectors \( l \) through \( m \) and sectors \( 1 \) through \( r \) are affected. Every affected station collects \( a \) samples from the event.

Your task is to determine for each member state the index of the meteor shower event after which the cumulative samples collected across all of its stations meet or exceed its declared target. If a state never meets its target, output -1 for that state.

Input Format (detailed below):

• The first line contains three integers \( n, m, q \): the number of states, the number of sectors, and the number of meteor shower events.
• The second line contains \( m \) integers. The \( i \)-th integer indicates the state (an integer between 1 and \( n \)) to which the \( i \)-th sector belongs.
• The third line contains \( n \) integers, where the \( j \)-th integer is the target number of samples for state \( j \).
• The next \( q \) lines each contain three integers \( l, r, a \) describing a meteor shower event: every station in the affected sectors gains \( a \) samples.

Output Format: Output \( n \) integers separated by spaces. The \( j \)-th integer should be the 1-indexed number of the meteor shower event after which state \( j \) reaches its target sample collection, or -1 if it never does.

Note: Sectors are arranged in a circular fashion; thus sectors 1 and \( m \) are adjacent.

inputFormat

The input begins with a line containing three integers \( n \), \( m \), and \( q \).
The second line contains \( m \) space-separated integers, where the \( i \)-th integer indicates the state to which the \( i \)-th sector belongs (states are numbered from 1 to \( n \)).
The third line contains \( n \) integers where the \( j \)-th integer is the sample collection target for state \( j \).
Each of the following \( q \) lines contains three integers \( l \), \( r \), and \( a \) representing a meteor shower event. If \( l \le r \), sectors \( l \) to \( r \) (inclusive) are affected; if \( l > r \), then sectors \( l \) through \( m \) and sectors \( 1 \) through \( r \) are affected.

outputFormat

Output a single line with \( n \) space-separated integers. The \( j \)-th integer is the event index after which state \( j \) reaches or exceeds its target, or -1 if it never does.

sample

3 6 5
1 2 1 3 2 2
5 10 3
1 3 2
4 1 1
5 2 3
3 6 1
2 4 2

2 3 5