POLSKI SPOJ

Dana jest tablica liczb A[1..N]. Napisz program, który będzie:

0) wykonywał modyfikacje tablicy A postaci: A[nr]:=w

1) odpowiadał na zapytania: ile razy w danym przedziale A[a..b] występuje element x

Input

W pierwszej linii podana jest liczba N - długość tablicy. (1<=N<=2*10^5)

W drugiej linii następuje N liczb A[1], A[2], ..., A[N] - początkowa zawartość tablicy.

W kolejnej linii zapisana jest liczba Q - liczba poleceń do wykonania. (0<=Q<=2*10^5).

Kolejne Q linii zawierają po jednym poleceniu. Są one postaci:

0 nr w  - ustaw wartość elementu A[nr] na w, 1<=nr<=N

1 a b x - policz wystąpienia elementu x w A[a..b], 1<=a<=b<=N

Wszystkie elementy tablicy, zarówno na początku jak i po wykonaniu modyfikacji będą z przedziału [0,10^9]. Elementy x, w zawsze będą z przedziału [0,10^9].

Output

Dla każdego polecenia typu 1 wypisz wynik zapytania.

Example

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

Output:
1
0
0
2