W spokojnym ogrodzie azalii pojawiło się $n$ niebezpiecznych stworzeń. Każde ma siłę ataku i siłę obrony. Początkowo $i$-te stworzenie ($1 \le i \le n$) ma siłę ataku $a_i$ i siłę obrony $b_i$.

Jako strażnik ogrodu azalii możesz wyobrazić sobie wojnę między nimi. Wojna składa się z kilku bitew (może ich być $0$). W każdej wyobrażonej bitwie wybierasz dwa żywe stworzenia $i$ i $j$ ($1 \le i,j \le n$, $i \ne j$), a następnie:

• Jeżeli siła ataku stworzenia $i$ jest większa lub równa sile obrony stworzenia $j$ (czyli $a_i \ge b_j$), to $i$ może pokonać $j$ w bitwie, a $j$ zostaje uznane za wyeliminowane.
• W przeciwnym razie nic się nie dzieje.

Pamiętaj, że wojny są wyobrażone: wyeliminowane stworzenie nie może brać udziału w dalszych bitwach tej samej wojny, ale odzyskuje siły na początku następnej wojny i może uczestniczyć w bitwach kolejnych wojen.

Stworzenia są niestabilne i z czasem ulegają mutacjom. Otrzymujesz $q$ mutacji. Po każdej z nich zmieniają się cechy jednego stworzenia. Konkretnie, podczas $i$-tej mutacji siła ataku $v_i$-tego stworzenia zmienia się na $x_i$, a siła obrony na $y_i$. Mutacje są trwałe: po $i$-tej mutacji skutki pierwszych $i-1$ mutacji nadal się kumulują.

Ponieważ każde pozostałe stworzenie nadal zagraża kwiatom, chcesz znaleźć najmniejszą możliwą liczbę stworzeń pozostałych po optymalnym ciągu bitew wyobrażonej wojny. Odpowiedz dla wszystkich stanów: przed wszystkimi mutacjami i po każdej mutacji.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n$ i $q$ ($1 \le n \le 4 \cdot 10^5$, $0 \le q \le 4 \cdot 10^5$), gdzie $n$ to liczba stworzeń, a $q$ to liczba mutacji.

Kolejne $n$ wierszy opisuje wszystkie stworzenia. $i$-ty z nich zawiera dwie liczby całkowite $a_i$ i $b_i$ ($1 \le a_i,b_i \le 10^9$), gdzie $a_i$ jest siłą ataku, a $b_i$ siłą obrony $i$-tego stworzenia.

Kolejne $q$ wierszy opisuje wszystkie mutacje. $i$-ty z nich zawiera trzy liczby całkowite $v_i$, $x_i$ i $y_i$ ($1 \le v_i \le n$, $1 \le x_i,y_i \le 10^9$), gdzie $x_i$ jest nową siłą ataku stworzenia $v_i$, a $y_i$ nową siłą obrony stworzenia $v_i$.

Wyjście

Wypisz $q+1$ wierszy, każdy z jedną liczbą całkowitą: kolejno odpowiedzi przed jakąkolwiek mutacją i po każdej mutacji.

Przykład

Wejście 1

3 1
1 1
2 2
3 3
2 2 4

Wyjście 1

1
2

Uwagi

W przykładzie, zanim zaczną się mutacje, trzecie stworzenie może pokonać pierwsze i drugie. Jest to oczywiście optymalny ciąg wyobrażonych bitew, więc odpowiedź wynosi $1$.

Po pierwszej mutacji siła ataku drugiego stworzenia wynosi $2$, a jego siła obrony $4$. Teraz trzecie stworzenie może pokonać tylko pierwsze, więc pozostają $2$ stworzenia. Można udowodnić, że nie istnieje lepsze rozwiązanie, zatem odpowiedź wynosi $2$.