Gigel are un șir cu N beculețe, numerotate de la 1 la N, inițial toate stinse. Cu acest șir Gigel face M operații, de două tipuri:

• 1 i j: toate beculețe numerotate cu valori între i și j își schimbă starea
• 2 k: se determină starea beculețului numerotat cu k.

Cerința

Scrieți un program care să determine citește N, M și cele M operații și determină rezultatul fiecărei operații de tipul 2.

Date de intrare

Fișierul de intrare beculete2.in conține pe prima linie numerele N M, separate printr-un spațiu, iar pe următoarele M linii operațiile.

Date de ieșire

Fișierul de ieșire beculete2.out va conține mai multe linii, fiecare conținând A sau S – rezultatul operației 2 corespunzătoare (Aprins sau Stins).

Restricții și precizări

• 1 ≤ N ≤ 1.000.000.000
• 1 ≤ M ≤ 100.000
• enunțul este identic cu cel al problemei beculete1, diferă N si M

Exemplu:

beculete2.in

7 5
1 2 5
2 4
1 3 6
2 4
2 7

beculete2.out

A
S
S

Explicație

Sunt două operații de tip 1 și trei operații de tip 2.
Inițial șirul de beculețe este: SSSSSSS
După prima operație șirul devine: SAAAASS
În acest moment starea beculețului 4 este A – aprins
După a treia operație șirul devine: SASSSAS
În acest moment starea beculețului 4 este S – stins
În acest moment starea beculețului 7 este S – stins