Archiwum zadań programistycznych WWSI

Dom sołtysa pewnej wsi otacza płot złożony z n sztachet ponumerowanych od 0 do n-1. Płot ten od lat nie był malowany i wygląda naprawdę obskurnie. Nasz gospodarz postanowił to zmienić. Zamierza on poprosić mieszkańców wsi, aby każdy z nich pomalował dowolnie wybrany fragment płotu. Zanim jednak to uczyni potrzebny jest mu system informatyczny umożliwiający wykonywanie dwóch rodzajów operacji:

• 0 a b - oznaczenie fragmentu płotu od sztachety a-tej do b-tej jako pomalowanego.
• 1 a b - obliczenie ile sztachet w przedziale od a-tej do b-tej jest pomalowanych.

Twoim zadaniem jest stworzenie tego systemu.

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite n ∈ [1;200000] i m ∈ [1;200000] oznaczające odpowiednio: liczbę sztachet wchodzących w skład ogrodzenia oraz liczbę operacji do wykonania. W kolejnych m liniach znajdują się polecenia.

Każda operacja składa się z trzech liczb: t ∈ [0;1], a ∈ [0;n-1] i b ∈ [a;n-1] oznaczających odpowiednio typ operacji oraz granice przedziału, na którym operujemy.

Wyjście

Dla każdego polecenia typu 1 należy, w osobnej linii wypisać, liczbę pomalowanych sztachet w przedziale [a;b].

Przykład

Wejście

10 5
0 2 4
0 8 9
1 3 8
0 7 7
1 0 7

Wyjście

3
4