Problem description

Jasiu przeciętny konsument struktury danych set odkrył ostatnio coś jeszcze lepszego – policy_based_data_structure, tak zwanego PBDSa. Jasiu i jego PBDSik szybko zostali przyjaciółmi. Jaś poczuł moc możliwości oznaczonego seta, jego PBDS-ik pozwalał na rozwiązywanie zadań, o jakich przyjaciołom Jasia nawet się nie śniło i to zaledwie w kilka linijek! Niestety ta opowieść nie kończy się “Happy endem”. Przyszedł złośliwy Marcel i dał brutalne limity czasu. Szczęśliwy Jasiu wraz ze swoim przyjacielem PBDS-siem oczywiście podjęli próbę walki z zadaniem złośliwego Marcela. Jednak zadanie Marcela znokautowało biednego PBDS-ika, PBDS-ik trafił do szpitala. Twoim zadaniem będzie pomóc Jasiowi pomścić biednego PBDS-ika i pokonać zadanie Marcela.

Napisz strukturę danych, która umożliwi następujące operacje:

• + X jeśli nie ma liczby X w zbiorze, to dodaj liczbę X do zbioru.

• - X jeśli liczba X jest w zbiorze, to usuń liczbę X ze zbioru.

• ? A B powiedz, ile liczb w zbiorze jest większych, bądź równych A i mniejszych, bądź równych B.

By Jaś nie mógł oszukać Marcela na wejściu zamiast liczby X podana będzie liczba Y. Liczbę X będzie można wyznaczyć wzorem Y^T mod  N, gdzie T to odpowiedź na poprzednią operację typu ?. Jeśli na wejściu nie było jeszcze operacji typu ? to przyjmij T równe 1.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i Q, oddzielone pojedynczym odstępem i oznaczające odpowiednio stałą N z zadania i liczbę operacji do wykonania. W kolejnych Q wierszach znajdują się opisy operacji, zgodne z opisem w treści zadania.

Wyjście

Na wyjście należy wypisać dla każdego zapytania typu ? jedną liczbę naturalną – liczbę liczb ze zbioru z odpowiedniego przedziału.

Ograniczenia

0 ≤ Q ≤ 100 000, 2 ≤ N ≤ 10¹⁸, 0 ≤ Y, A, B < N.

Przykład

5 5
+ 2
+ 3
? 2 4
- 4
? 0 4

2
2