baruri

Baruri

Pe strada Lipscani sunt N baruri. Cum Antonio se duce pe Lipscani in fiecare seara, vrea sa stie cati prieteni are in barurile din jur, sa se intalneasca cu ei.
Astfel Antonio a facut o aplicatie care raspunde la intrebari de tipul: $"Cati prieteni sunt la o distanta de maxim D baruri de locatia lui?"$.

Cum nici el nici prietenii lui nu pot sta pe loc, aplicatia trebuie sa stie cine in ce bar pleaca.

Cum nici el nici prietenii lui nu pot sta pe loc, aplicatia trebuie sa stie unde se muta prietenii.

h2. Date de intrare

Pe a doua linie se afla $N$ numere, al i-lea numar semnificand numarul de prieteni din barul i.
Pe a treia linie se afla $M$, numarul de operatii.
Pe urmatoarele $M$ linii se afla operatii:

* $0 B D$ - Afiseaza cati prieteni sunt in barurile de la o distanta de maxim D baruri fata de barul $B$ in care este Antonio. Cei care sunt deja in barul $B$ sunt in gasca lui deci nu se iau in considerare.

* $1 X B1 B2$ - $X$ prieteni se muta din barul $B1$ in barul $B2$.

* $1 X B$ - $X$ prieteni noi intra in barul $B$.
* $2 X B$ - $X$ prieteni din barul $B$ pleaca de pe Lipscani.
* $3 X B1 B2$ - $X$ prieteni se muta din barul $B1$ in barul $B2$.

h2. Date de ieşire

În fişierul de ieşire $baruri.out$ se vor afisa raspunsurile la intrebarile lui Antonio, in ordinea in care apar.

În fişierul de ieşire $baruri.out$ se vor afisa raspunsurile la intrebari (operatii de tipul 0), in ordinea in care apar.

h2. Restricţii

* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 150 000$
* $1 ≤ A, B ≤ N$

* $X ≤ 10 000$

* $D ≥ 1$

* Numerele se vor incadra pe 32 de biti.

* Desi Antonio este foarte popular, numarul de prieteni va putea fi reprezentat pe 32 de biti cu semn

h2. Exemplu

2 1 2 0 0
3
0 2 1

1 2 1 5

3 2 1 5

0 2 1
| 4
  2
|

h3. Explicaţie
...

== include(page="template/taskfooter" task_id="baruri") ==

9530