Задача Космодром

Описание

В космодроме планеты Эллента системы Альдиба есть N залов ожидания. Они расположены кольцом, поэтому можно подойти со стороны любого зала. Залы пронумерованны от 1 до N по направлению часовой стрелки. Каждый зал имеет свою вместимость, поэтому никто не может войти в него, если там нет свободных мест.

Каждый человек, подходя к одному из залов ожидания, начинает обходить все залы по или против направления часовой стрелки пока не найдет свободное место, и занимает его. За сегодняшний день космодром посетило M человек. Для каждого из них известны номер зала, со стороны которого он подошел, время его прихода, время его ухода и направление, в котором он начал искать зал.

Ваша задача - для каждого из людей определить номер зала, в котором он остановился. Предполагается, что обход человек совершает мгновенно. Гарантируется, что никакие два события не происходят в одно и то же время и каждый человек сможет найти себе место.

Формат входных данных

В первой строке входного файла содержится одно число N. (1 <= N <= 100000) Далее следуют N строк по одному числу:
i-ое число - вместимость i-ого зала. (сумма всех вметимостей не больше 100000) На следущей строке находится число M. (1 <= M <= 100000) После следуют M строк, описывающих приходящих людей.
j-ая строка содержит 4 числа A _j , T1 _j , T2 _j , D _j , описывающие j-ого человека:
A _j - номер зала, к которому он подошел (1 <= A _j <= N) T1 _j - время прихода в космодром (1 <= T1 _j < 10 ⁹ ) T2 _j - время, когда он покинул космодром (T1 _j < T2 _j <= 10 ⁹ ) D _j - напраление поиска зала (D _j = 1, если движение по часовой стрелке, и D _j = -1 - если против)

Формат выходных данных

В выходной файл выведите M чисел, по одному на каждой строке. i-ое число - номер зала от 1 до N, в котором остановился i-ый человек.