Перед приемом к двум врачам выстроились \(2\) очереди пациентов. Первый врач принимает пациентов в обычном порядке очереди — кто раньше пришел, того он раньше и примет. А второй врач делает наоборот — принимает сначала тех, кто пришел позже всех. То есть, к первому врачу стоит очередь, а ко второму — стек. Один пациент может одновременно стоять и в очереди, и в стеке. Каждый пациент характеризуется временем, которое займет его визит ко врачу (время одинаковое для обоих врачей).
Когда начнется прием, врачи будут принимать пациентов в порядке очереди и стека соответственно. Как только врач закончит с одним пациентом, он вызовет следующего.
Но есть одна проблема: если пациент стоял и в очереди, и в стеке, и его вызвали сначала к одному врачу, а потом к другому, пока он не успел выйти от первого, начнется неразбериха. Допустимо, чтобы пациент пошел ко второму врачу в тот же момент времени, в который вышел от первого врача.
Текущая конфигурация очереди и стека называется хорошей, если врачи могут принять всех пациентов, и при этом не возникнет неразбериха.
Изначально очередь и стек пусты. Поступают запросы трех типов:
- добавить пациента \(x\) в очередь;
- добавить пациента \(x\) в стек;
- пациент \(x\), стоявший в очереди, понимает, что он стоит не туда и перемещается в стек; при этом он перемещается на то место в стеке, как если бы он встал в стек в момент запроса, когда он встал в очередь.
Гарантируется, что после каждого запроса каждый пациент занимает не более одного места в очереди и не более одного места в стеке.
После каждого запроса нужно узнать, является ли конфигурация хорошей.
Выходные данные
После каждого запроса выведите «YES», если текущая конфигурация является хорошей, и «NO» в противном случае.
Примечание
В первом тесте следующие конфигурации:
- очередь: \([1]\); стек: \([]\); пациента \(1\) первый врач принимает \(10\) минут, начиная с минуты \(0\).
- очередь: \([1]\); стек: \([1]\); пациента \(1\) первый врач принимает во время \([0; 10)\) и второй во время \([0; 10)\). Так как пациент \(1\) должен одновременно быть у двух врачей, ответ «NO».
- очередь: \([1]\); стек: \([1, 2]\); пациента \(1\) первый врач принимает во время \([0; 10)\), а второй во время \([15; 25)\); пациента \(2\) второй врач принимает во время \([0, 15)\). Теперь пациент \(1\) успевает ко второму врачу после приема у первого.
Во втором тесте конфигурации после запроса \(4\) следующая конфигурация:
- очередь: \([1, 2]\);
- стек: \([5, 3]\);
- пациент \(1\): первый врач \([0, 2)\), второй врач не принимает;
- пациент \(2\): первый врач \([2, 7)\), второй врач не принимает;
- пациент \(3\): первый врач не принимает, второй врач \([0, 1)\);
- пациент \(5\): первый врач не принимает, второй врач \([1, 6)\).
После запроса \(5\) следующая конфигурация:
- очередь: \([1]\);
- стек: \([5, 2, 3]\);
- пациент \(1\): первый врач \([0, 2)\), второй врач не принимает;
- пациент \(2\): первый врач не принимает, второй врач \([1, 6)\);
- пациент \(3\): первый врач не принимает, второй врач \([0, 1)\);
- пациент \(5\): первый врач не принимает, второй врач \([6, 11)\).
После запроса \(6\) следующая конфигурация:
- очередь: \([1, 2]\);
- стек: \([5, 2, 3]\);
- пациент \(1\): первый врач \([0, 2)\), второй врач не принимает;
- пациент \(2\): первый врач \([2, 7)\), второй врач \([1, 6)\);
- пациент \(3\): первый врач не принимает, второй врач \([0, 1)\);
- пациент \(5\): первый врач не принимает, второй врач \([6, 11)\).
Пациент \(2\) должен быть у двух врачей одновременно.
После запроса \(7\) следующая конфигурация:
- очередь: \([2]\);
- стек: \([1, 5, 2, 3]\);
- пациент \(1\): первый врач не принимает, второй врач \([11, 13)\);
- пациент \(2\): первый врач \([0, 5)\), второй врач \([1, 6)\);
- пациент \(3\): первый врач не принимает, второй врач \([0, 1)\);
- пациент \(5\): первый врач не принимает, второй врач \([6, 11)\).
Пациент \(2\) должен быть у двух врачей одновременно.