Masz dany ciąg liczb A zawierający N elementów (indeksowanych od 1). Napisz program umożliwiający wykonywanie następujących operacji na tym ciągu:

Query() - znajdź i wypisz największą X, gdzie X = a_j-a_i, j ≥ i, oraz a_j i a_i są elementami ciągu A.

Update(p, v) - Zmień wartość elementu a_p na v.

Wejście

W pierwszej linii dwie liczby: N i Q oznaczające kolejno ilość elementów w ciągu A oraz ilość zapytań.

W kolejnej linii znajduje się N liczb z przedziału [1..10⁹], gdzie i'ta liczba oznacza wartość i'tego elementu ciągu A.

W kolejnych Q liniach znajdują się zapytania opisane w następujący sposób:

q - Jeden znak 'q' oznacza, że program ma zwrócić wartość zapytania Query().

u p v - Znak 'u' oraz dwie liczby p i v oznaczają, że program ma wykonać operację Update(p,v).

Wyjście

Dla każdego zapytania Query() znajdź i wypisz największą X.

Wszystkie X mają być oddzielone (enterem).

Limity

1 ≤ N ≤ 50000 (długość ciągu A)

1 ≤ a_i ≤ 10⁹ (wartości elementów ciągu A)

1 ≤ Q ≤ 50000 (ilość zapytań)

1 ≤ p ≤ N (indeks elementu któremu należy zmienić wartość w operacji Update(p,v))

1 ≤ v ≤ 10⁹ (wartość nadawana elementowi a_p podczas wykonywania operacji Update(p,v))

Przykłady

Wejście 1:

10 6
2 6 8 5 1 5 6 5 3 3
q
u 5 10
q
u 1 5
u 5 3
q

Wyjście 1:
6
8
3

Wejście 2:

5 7
3 6 6 2 6
q
u 2 7
u 1 1
q
u 2 10
q
u 2 3

Wyjście 2:

4
6
9