Метеоры
Ужляндское межзвездное содружество (УМС) недавно обнаружило новую планету в ближайшей галактике. К сожалению, она не годится для колонизации из-за странных метеоритных дождей, что с другой стороны делает эту планету очень интересным объектом наблюдения.
Члены - государства УМС уже расположили космические станции недалеко от орбиты планеты. Цель станций – собрать образцы камней, пролетающих там. Комиссия УМС поделила орбиту на m секторов, пронумерованных от 1 до m (сектор 1 и сектор m являются соседними). В каждом секторе располагается единственная космическая станция, принадлежащая одному из n государств-членов.Каждое государство сообщило количество камней-образцов, которые оно намеревается собрать до конца миссии. Ваша цель - для каждого государства определить, когда оно может перестать брать образцы, основываясь на прогнозе метеоритных дождей на ближайшие несколько лет.
Входные данные
Первая строка стандартного ввода задает два целых числа, n и m(1 ≤ n; m ≤ 3*10^5), разделенные одним пробелом, которые обозначают, соответственно, число государств - членов УМС и число секторов.
Во второй строке дано m целых чисел o[i](1 ≤ o[i] ≤ n), разделенных пробелами, которые обозначают номер государства, владеющего космической станцией.
В третьей строке дано n целых чисел p[i] (1 ≤ p[i] ≤ 10^9), разделенных пробелами, которые обозначают число образцов метеоров, которые каждое государство намеревается собрать.
В четвертой строке есть одно целое число k(1 ≤ k ≤ 3*10^5) , что означает число предсказаний метеорных дождей. Следующие строки указывают(прогноз) метеоритные дожди в хронологическом порядке. Каждая строка содержит три целых числа l; r; a (разделенных пробелами), которые обо-значают, что метеоритный дождь, как ожидается, пройдет в секторах l; l + 1; ..; r если l ≤ r или в секторах l; l + 1; ..; m; 1; ..; r в противном случае, во время которого на каждую станцию выпадет a образцов метеоритов.
Выходные данные
Ваша программа должна вывести n строк. i-тая из них должна содержать одно целое число, обозначающее количество метеоритных дождей, после которых, i-тая станция соберет требуемое количество образцов - метеоритов или 1 если ей это не удастся.