Matrix Search
Национална Олимпиада по Информатика 2016, Кръг 3
Time Limit: 2s, Memory Limit: 64MiB
Ели се подготвя за интервю. Днес тя попадна на доста стандартна задача, която обаче става далеч по-интересна с малка модификация. В нейния вариант задачата е следната:

Дадена ви е матрица от цели числа с N реда и M колони. Числата Aij във всеки ред 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 ≤ RiN ≤ 1,000
  • 1 ≤ CiM ≤ 1,000
  • 1 ≤ Aij ≤ 1,000,000,000
  • 1 ≤ Q ≤ 20,000
  • 1 ≤ Xi ≤ 2,000,000,000
  • 1 ≤ Yi ≤ 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
Мрън!