Сезон Красноярской Летней Школы подходит к концу, впереди дискотека предпоследнего дня. Каждый летнешкольник мечтает сесть за диджейский пульт на этом мероприятии - и, кажется, вам улыбнулась удача!

Пока вы готовили плейлист на вечер, вы узнали, что у каждого трека есть целых три целочисленных параметра: $a$ (битрейт), $b$ (удары в минуту) и $c$ (насколько трек напоминает hardbass). Из этих параметров можно вычислить, насколько трек крут, по формуле: $a^{(b^c)}$ Все параметры могут принимать значение от $1$ до $k$.

Разобравшись с этими параметрами и составив наконец плейлист из $n$ треков, вы и не заметили, к вам выстроилась очередь из $q$ человек - и у каждого к вам есть важная просьба. Просьбы делятся на два типа:

1. put i a b c - поставить на позицию $i$ трек с параметрами $a$, $b$ и $c$.
2. best l r - узнать крутость самого крутого трека в диапазоне от трека на позиции $l$ до трека на позиции $r$ включительно. (номера треков считаются с единицы; нужно учитывать изменения, сделанные по просьбе типа put).

Чтобы вас не сместили с позиции диджея, напишите программу, которая обработает все эти просьбы и ответит на них.

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

В первой строке входных данных записаны числа $n$, $k$ и $q$ - количество треков в плейлисте, максимальное значение для любого из параметров трека и количество просьб соответственно ($1 \le n, k, q \le 10^5$).

В следующих $n$ строках записаны числа $a_i$, $b_i$ и $c_i$ - параметры трека, изначально стоящего на $i$-той позиции в плейлисте. ($1 \le a, b, c \le k$)

В следующих $q$ строках записаны просьбы (запросы) вида put i a b c ($1 \le a, b, c \le k$) и best l r ($1 \le l\le r \le n$), в каждой строке по одной просьбе.

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

В ответ на каждую просьбу (запрос) вида best l r выведите значение самого крутого трека в диапазоне от трека на позиции l до трека на позиции r включительно. Так как трек может быть слишком крутым, ответ нужно вывести по модулю $10^9 + 17542$.

Подзадачи