Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FASTMAX - Maksimum w przedziale

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

Dodane przez:Przemek Komosa
Data dodania:2010-10-31
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.