Meteors
The Uzhland Interstellar Commonwealth (UIC) has recently discovered a new planet in a nearby galaxy. Although the planet is unsuitable for colonization due to unusual meteor showers, these phenomena make it a fascinating subject for observation.
The UIC member states have already deployed space stations near the planet's orbit. These stations are tasked with collecting rock samples from the meteor showers. The UIC commission has divided the orbit into m sectors, numbered from 1 to m (with sector 1 adjacent to sector m). Each sector hosts a space station operated by one of the n member states. Each state has specified the number of rock samples it aims to collect by the mission's end. Your task is to determine when each state can stop collecting samples, based on the meteor shower forecasts for the upcoming years.
Input
The first line of input contains two integers, n and m (1 ≤ n, m ≤ 3 × 10^5), separated by a space, representing the number of UIC member states and the number of sectors, respectively.
The second line contains m integers o[i] (1 ≤ o[i] ≤ n), separated by spaces, indicating the state that owns the space station in each sector.
The third line contains n integers p[i] (1 ≤ p[i] ≤ 10^9), separated by spaces, representing the number of meteor samples each state plans to collect.
The fourth line contains a single integer k (1 ≤ k ≤ 3 × 10^5), indicating the number of meteor shower predictions. The following k lines describe the meteor showers in chronological order. Each line contains three integers l, r, and a (separated by spaces), indicating that a meteor shower is expected to occur in sectors l to r if l ≤ r, or in sectors l to m and 1 to r otherwise. During this shower, each station in the affected sectors will receive a samples of meteorites.
Output
Your program should output n lines. The i-th line should contain a single integer indicating the number of meteor showers after which the i-th state will have collected the required number of meteor samples, or -1 if it will not succeed.