Ели се подготвя за интервю. Днес тя попадна на доста стандартна задача, която обаче става далеч по-интересна с малка модификация. В нейния вариант задачата е следната:

Дадена ви е матрица от цели числа с N реда и M колони. Числата A_ij във всеки ред i от матрицата са в строго нарастващ ред. По-интересното е, че същото важи и за числата във всяка от колоните j – и те са в строго нарастващ ред.

Трябва да изпълните Q на брой заявки, всяка от които е от един от следните два типа:

1. "1 X", на която трябва да отговорите дали числото X се съдържа в матрицата.
2. "2 R C Y", на която трябва да добавите Y към всяко от числата в матрицата, които се намират надолу и надясно (включително) от клетката с ред R и колона C.

На първия ред на стандартния вход ще бъдат зададени целите числа N и M – съответно броя редове и броя колони на матрицата с числа. Следват N на брой реда, всеки съдържащ по M цели числа – първоначалните стойности на числата в матрицата. На следващия ред ще бъде зададено цялото число Q – колко на брой заявки ще зададе Ели. Следват Q на брой реда, всеки задаващ по една от описаните по-горе заявки. За всяка от заявките от тип 1) изведете на отделен ред на стандартния изход 'Y' ако числото се съдържа сред текущите стойности на матрицата, и 'N' в противен случай.

• 1 ≤ R_i ≤ N ≤ 1,000
• 1 ≤ C_i ≤ M ≤ 1,000
• 1 ≤ A_ij ≤ 1,000,000,000
• 1 ≤ Q ≤ 20,000
• 1 ≤ X_i ≤ 2,000,000,000
• 1 ≤ Y_i ≤ 50,000

Примерен Вход	Примерен Изход
3 4 11 13 14 17 13 15 19 21 18 20 23 42 9 1 42 1 27 2 2 2 4 1 27 2 1 3 7 1 20 1 32 1 19 1 42	Y N Y N Y Y N