{"raw_statement":[{"iden":"statement","content":"Великий физик современности Берлштейн занимается изучением световых явлений. И прямо сейчас он готовит экспериментальную установку для изучения интерференции (явления наложения двух и более световых волн).\n\nУстановка должна состоять из N прожекторов, расположенных в одну линию. Каждый прожектор излучает свет определённой длины волны, от которой зависит цвет света. Когда прожектор включается, на экране, который расположен вдоль линии, параллельной линии прожекторов, появляется полоса определённого цвета. Зона экрана, освещаемая i-м прожектором, определяется целочисленными координатами Li и Ri.\n\nЗоны экрана, освещаемые различными прожекторами, могут перекрываться. Вследствие этого световые волны, излучаемые прожекторами, могут интерферировать между собой, образуя на экране полосу нового цвета. Эксперимент проводится в специальной комнате, в которой интерференция происходит по следующим правилам:\n\nВ ходе своего эксперимента Берлштейн включает прожекторы в определённые моменты времени Ti. В результате к концу эксперимента на экране наблюдаются полосы различных цветов. Для корректного выполнения расчётов Берлштейну необходимо знать, наблюдается ли интерференционная картина в точках экрана Xj в моменты времени Tj. А если не наблюдается, то по какой причине (интерференции в принципе не может быть или же точку освещают несовместимые световые волны).\n\nПервая строка содержит целое число N (1 ≤ N ≤ 105) — количество прожекторов. \n\nСледующие N строк описывают прожекторы. Каждая из них содержит целые числа Li, Ri и Ti (0 ≤ Li ≤ Ri ≤ 105, 0 ≤ Ti ≤ 105), а также строчную латинскую букву Ci — соответственно границы зоны экрана, освещаемой i-м прожектором, момент времени, в который включается i-й прожектор, и цвет света, излучаемого i-м прожектором.\n\nСледующая строка содержит целое число M (0 ≤ M ≤ 1000) — количество моментов времени, интересующих Берлштейна.\n\nСледующие M строк описывают моменты времени и точки, в которых Берлштейн выясняет наличие интерференции. Каждая из них содержит целые числа Tj и Xj (0 ≤ Tj ≤ 105, 0 ≤ Xj ≤ 105) — соответственно момент времени и координату точки экрана, в которой проверяется существование интерференционной картины.\n\nСледующие строки (не более 1000) содержат описание совместимых наборов цветов. Каждая из них содержит последовательность строчных латинских букв (не менее 2 и не более 100), обозначающих совместимые цвета, и строчную латинскую букву, обозначающую результирующий цвет. Гарантируется, что каждый набор цветов встречается во входных данных не более одного раза.\n\nДля каждого момента времени Tj и точки экрана Xj, расположенных в порядке возрастания момента времени, в отдельную строку выходного файла поместите «YES», если интерференционная картина в данный момент времени в данной точке наблюдается, «NO», если точку освещают несовместимые световые волны, и «NO INTERFERENCE», если интерференции вообще быть не может.\n\n"},{"iden":"входные данные","content":"Первая строка содержит целое число 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), обозначающих совместимые цвета, и строчную латинскую букву, обозначающую результирующий цвет. Гарантируется, что каждый набор цветов встречается во входных данных не более одного раза."},{"iden":"выходные данные","content":"Для каждого момента времени Tj и точки экрана Xj, расположенных в порядке возрастания момента времени, в отдельную строку выходного файла поместите «YES», если интерференционная картина в данный момент времени в данной точке наблюдается, «NO», если точку освещают несовместимые световые волны, и «NO INTERFERENCE», если интерференции вообще быть не может."},{"iden":"примеры","content":"Входные данные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"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of branches.  \nLet $ 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.  \nLet $ \\mathbf{y} = (y_1, \\dots, y_N)^\\top \\in \\mathbb{R}^N $ be the vector of last year’s retail sales per branch.  \nLet $ \\mathbf{d} = (d_1, \\dots, d_N)^\\top \\in \\mathbb{R}^N $ be the vector of planned retail sales this year.  \n\nAssume last year’s production vector $ \\mathbf{p} = (p_1, \\dots, p_N)^\\top $ satisfied:  \n$$\np_i = \\sum_{j=1}^N c_{ji} + y_i \\quad \\forall i \\in \\{1, \\dots, N\\}\n$$\n\nAssume proportionality: the consumption matrix scales linearly with production. Define the **input coefficient matrix** $ A = [a_{ij}] \\in \\mathbb{R}^{N \\times N} $, where:  \n$$\na_{ij} = \\frac{c_{ji}}{p_j} \\quad \\text{(from last year's data)}\n$$\n\n**Constraints**  \n1. $ 1 \\le N \\le 3000 $  \n2. $ 1 \\le c_{ij} \\le 1000 $  \n3. $ 10^7 \\le y_i \\le 10^9 $  \n4. $ 10^7 \\le d_i \\le 10^9 $  \n\n**Objective**  \nCompute the production vector $ \\mathbf{x} = (x_1, \\dots, x_N)^\\top \\in \\mathbb{R}^N $ this year such that:  \n$$\n\\mathbf{x} = A \\mathbf{x} + \\mathbf{d}\n$$  \nor equivalently,  \n$$\n(I - A)\\mathbf{x} = \\mathbf{d}\n$$\n\nSolve for $ \\mathbf{x} $.","simple_statement":"Given N branches, each branch i produces some product. Last year, branch i sent c[i][j] tons to branch j, and sold y[i] tons to retailers. This year, branch i must sell p[i] tons to retailers. The amount each branch needs from others is proportional to its own production. Compute how much each branch must produce this year so that supply equals demand.","has_page_source":false}