Великий физик современности Берлштейн занимается изучением световых явлений. И прямо сейчас он готовит экспериментальную установку для изучения интерференции (явления наложения двух и более световых волн).
Установка должна состоять из N прожекторов, расположенных в одну линию. Каждый прожектор излучает свет определённой длины волны, от которой зависит цвет света. Когда прожектор включается, на экране, который расположен вдоль линии, параллельной линии прожекторов, появляется полоса определённого цвета. Зона экрана, освещаемая i-м прожектором, определяется целочисленными координатами Li и Ri.
Зоны экрана, освещаемые различными прожекторами, могут перекрываться. Вследствие этого световые волны, излучаемые прожекторами, могут интерферировать между собой, образуя на экране полосу нового цвета. Эксперимент проводится в специальной комнате, в которой интерференция происходит по следующим правилам:
В ходе своего эксперимента Берлштейн включает прожекторы в определённые моменты времени 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», если интерференции вообще быть не может.
## Входные Данные
Первая строка содержит целое число 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», если интерференции вообще быть не может.
## Примеры
Входные данные30 2 5 y1 4 0 b1 7 8 r60 01 15 27 38 110 3yb gВыходные данныеNO INTERFERENCENO INTERFERENCEYESNO INTERFERENCENONOВходные данные41 4 1 a2 4 2 b3 4 3 b4 4 4 b41 12 23 34 4ab qabbb yВыходные данныеNO INTERFERENCEYESNOYES
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of branches.
Let $ C = [c_{ij}] \in \mathbb{R}^{N \times N} $ be the consumption matrix, where $ c_{ij} $ is the amount of product from branch $ i $ consumed by branch $ j $ last year.
Let $ \mathbf{y} = (y_1, \dots, y_N)^\top \in \mathbb{R}^N $ be the vector of last year’s retail sales per branch.
Let $ \mathbf{d} = (d_1, \dots, d_N)^\top \in \mathbb{R}^N $ be the vector of planned retail sales this year.
Assume last year’s production vector $ \mathbf{p} = (p_1, \dots, p_N)^\top $ satisfied:
$$
p_i = \sum_{j=1}^N c_{ji} + y_i \quad \forall i \in \{1, \dots, N\}
$$
Assume proportionality: the consumption matrix scales linearly with production. Define the **input coefficient matrix** $ A = [a_{ij}] \in \mathbb{R}^{N \times N} $, where:
$$
a_{ij} = \frac{c_{ji}}{p_j} \quad \text{(from last year's data)}
$$
**Constraints**
1. $ 1 \le N \le 3000 $
2. $ 1 \le c_{ij} \le 1000 $
3. $ 10^7 \le y_i \le 10^9 $
4. $ 10^7 \le d_i \le 10^9 $
**Objective**
Compute the production vector $ \mathbf{x} = (x_1, \dots, x_N)^\top \in \mathbb{R}^N $ this year such that:
$$
\mathbf{x} = A \mathbf{x} + \mathbf{d}
$$
or equivalently,
$$
(I - A)\mathbf{x} = \mathbf{d}
$$
Solve for $ \mathbf{x} $.