Fișierul intrare/ieșire	ruine.in, ruine.out	Sursă	ad-hoc
Autor	Cătălin Frâncu	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.05 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Ruine

Într-o regiune turistică sunt N sate dispuse în linie. Inițial, oricare două sate vecine sunt unite printr-un drum. Cu timpul, drumurile se surpă și nimeni nu le repară. În fiecare sat i sunt T_i obiective turistice de vizitat. Biroul de Turism din regiune primește mesaje de două tipuri:

• primăriile anunță când un drum se surpă
• turiștii pun întrebări de forma: „Câte obiective pot fi vizitate în satul i și în satele la care se mai poate ajunge din i ”?

Date de intrare

Fișierul de intrare ruine.in conține pe prima linie numerele N și M, reprezentând numărul de state și numărul de mesaje primite de Biroul de Turism. Pe a doua linie se află N numere T₁, T₂, ..., T_N. Pe următoarele M linii sunt mesajele primite de Biroul de Turism, sub formele:

• S i — mesajul indică că drumul între satele i și i + 1 s-a surpat (1 ≤ i < N);
• T i — mesajul întreabă numărul total de obiective în satul i și în satele accesibile din i (1 ≤ i ≤ N).

Date de ieșire

În fișierul de ieșire ruine.out se vor tipări răspunsurile la interogările de tip „T”, câte unul pe linie, în ordinea în care au fost puse întrebările.

Restricții

• 1 ≤ N ≤ 1.000.000;
• 1 ≤ M ≤ 2.000.000;
• 1 ≤ T_i ≤ 1.000;

Exemplu