Ужляндское межзвездное содружество (УМС) недавно обнаружило новую планету в ближайшей галактике. К сожалению, она не годится для колонизации из-за странных метеоритных дождей, что с другой стороны делает эту планету очень интересным объектом наблюдения.

Члены - государства УМС уже расположили космические станции недалеко от орбиты планеты. Цель станций – собрать образцы камней, пролетающих там. Комиссия УМС поделила орбиту на m секторов, пронумерованных от 1 до m (сектор 1 и сектор m являются соседними). В каждом секторе располагается единственная космическая станция, принадлежащая одному из n государств-членов. Каждое государство сообщило количество камней-образцов, которые оно намеревается собрать до конца миссии. Ваша цель - для каждого государства определить, когда оно может перестать брать образцы, основываясь на прогнозе метеоритных дождей на ближайшие несколько лет.

Входные данные

Первая строка стандартного ввода задает два целых числа, n и m(1 ≤ n; m ≤ 3*105), разделенные одним пробелом, которые обозначают, соответственно, число государств - членов УМС и число секторов.

Во второй строке дано m целых чисел oi(1 ≤ oi ≤ n), разделенных пробелами, которые обозначают номер государства, владеющего космической станцией.

В третьей строке дано n целых чисел pi (1 ≤ pi ≤ 109), разделенных пробелами, которые обозначают число образцов метеоров, которые каждое государство намеревается собрать.

В четвертой строке есть одно целое число k(1 ≤ k ≤ 3*105) , что означает число предсказаний метеорных дождей. Следующие строки указывают(прогноз) метеоритные дожди в хронологическом порядке. Каждая строка содержит три целых числа l; r; a (разделенных пробелами), которые обо-значают, что метеоритный дождь, как ожидается, пройдет в секторах l; l + 1; ..; r если l ≤ r или в секторах l; l + 1; ..; m; 1; ..; r в противном случае, во время которого на каждую станцию выпадет a образцов метеоритов.

Выходные данные

Ваша программа должна вывести n строк. i-тая из них должна содержать одно целое число, обозначающее количество метеоритных дождей, после которых, i-тая станция соберет требуемое количество образцов - метеоритов или 1 если ей это не удастся.