Mały Jasio jeszcze nie umie programować, nie zna też algorytmów, więc ten problem jego nie dotyczy. Pozostali muszą rozwiązać pewien klasyczny problem. Dany jest ciąg liczb nieujemnych, który zmienia się w czasie. Możesz być zapytany w dowolnej chwili o największą wartość w pewnym przedziale.

Początkowo, wszystkie elementy ciągu są równe 0.

Input

Najpierw podane są dwie liczby dodatnie. N oznaczające ilość elementów w ciągu, oraz R oznaczające ilość zapytań.

N, R <= 2 * 10^5

Potem jest R linii, każda z nich zawiera trzy liczby:

q będące rodzajem zapytania, oraz parametry a i b

Jeśli q jest równe 1, to zapytanie polega na zaktualizowaniu elementu o indeksie a do wartości b (b <= 10^9)

Jeśli q posiada inną wartość, to na zapytanie należy odpowiedzieć największą liczbą w przedziale obustronnie domkniętym <a, b>, gdzie a, b są indeksami w ciągu (a <= b).

Elementy ciągu indeksujemy od 0 do (N - 1).

Output

Dla każdego zapytania, gdzie q jest różne od 1 należy wypisać żądaną wartość (największą w danym przedziale)

Example

Input:
5 6
1 1 1
1 2 2
1 3 4
1 4 2
0 0 4
0 4 4

Output:
4
2