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.|

MOREQ1 - Zapytania I

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

Dodane przez:Damian Straszak
Data dodania:2011-09-26
Limit czasu wykonania programu:0.100s-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.