A. Интерференция
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
input.txt
вывод
output.txt

Великий физик современности Берлштейн занимается изучением световых явлений. И прямо сейчас он готовит экспериментальную установку для изучения интерференции (явления наложения двух и более световых волн).

Установка должна состоять из N прожекторов, расположенных в одну линию. Каждый прожектор излучает свет определённой длины волны, от которой зависит цвет света. Когда прожектор включается, на экране, который расположен вдоль линии, параллельной линии прожекторов, появляется полоса определённого цвета. Зона экрана, освещаемая i-м прожектором, определяется целочисленными координатами Li и Ri.

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

  1. Интерферировать могут только исходные световые волны прожекторов;
  2. Интерферировать могут только определённые совместимые наборы волн. Если в некоторый момент времени набор всех световых волн, которыми освещена определённая точка экрана, не является совместимым, интерференция в данной точке не наблюдается.

В ходе своего эксперимента Берлштейн включает прожекторы в определённые моменты времени Ti. В результате к концу эксперимента на экране наблюдаются полосы различных цветов. Для корректного выполнения расчётов Берлштейну необходимо знать, наблюдается ли интерференционная картина в точках экрана Xj в моменты времени Tj. А если не наблюдается, то по какой причине (интерференции в принципе не может быть или же точку освещают несовместимые световые волны).

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

Первая строка содержит целое число N (1 ≤ N ≤ 105) — количество прожекторов.

Следующие N строк описывают прожекторы. Каждая из них содержит целые числа Li, Ri и Ti (0 ≤ Li ≤ Ri ≤ 105, 0 ≤ Ti ≤ 105), а также строчную латинскую букву Ci — соответственно границы зоны экрана, освещаемой i-м прожектором, момент времени, в который включается i-й прожектор, и цвет света, излучаемого i-м прожектором.

Следующая строка содержит целое число M (0 ≤ M ≤ 1000) — количество моментов времени, интересующих Берлштейна.

Следующие M строк описывают моменты времени и точки, в которых Берлштейн выясняет наличие интерференции. Каждая из них содержит целые числа Tj и Xj (0 ≤ Tj ≤ 105, 0 ≤ Xj ≤ 105) — соответственно момент времени и координату точки экрана, в которой проверяется существование интерференционной картины.

Следующие строки (не более 1000) содержат описание совместимых наборов цветов. Каждая из них содержит последовательность строчных латинских букв (не менее 2 и не более 100), обозначающих совместимые цвета, и строчную латинскую букву, обозначающую результирующий цвет. Гарантируется, что каждый набор цветов встречается во входных данных не более одного раза.

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

Для каждого момента времени Tj и точки экрана Xj, расположенных в порядке возрастания момента времени, в отдельную строку выходного файла поместите «YES», если интерференционная картина в данный момент времени в данной точке наблюдается, «NO», если точку освещают несовместимые световые волны, и «NO INTERFERENCE», если интерференции вообще быть не может.

Примеры
Входные данные
3
0 2 5 y
1 4 0 b
1 7 8 r
6
0 0
1 1
5 2
7 3
8 1
10 3
yb g
Выходные данные
NO INTERFERENCE
NO INTERFERENCE
YES
NO INTERFERENCE
NO
NO
Входные данные
4
1 4 1 a
2 4 2 b
3 4 3 b
4 4 4 b
4
1 1
2 2
3 3
4 4
ab q
abbb y
Выходные данные
NO INTERFERENCE
YES
NO
YES