Trong một khu vườn đỗ quyên yên bình, $n$ sinh vật nguy hiểm đã xuất hiện. Mỗi sinh vật có một sức tấn công và một sức phòng thủ. Ban đầu, sinh vật thứ $i$ ($1 \le i \le n$) có sức tấn công $a_i$ và sức phòng thủ $b_i$.

Bạn là người bảo vệ vườn đỗ quyên và có thể tưởng tượng trong đầu một cuộc chiến giữa chúng. Một cuộc chiến gồm một số trận đánh (có thể là $0$). Trong mỗi trận đánh tưởng tượng, bạn chọn hai sinh vật còn sống $i$ và $j$ ($1 \le i,j \le n$, $i \ne j$), và:

• Nếu sức tấn công của sinh vật $i$ lớn hơn hoặc bằng sức phòng thủ của sinh vật $j$ (tức là $a_i \ge b_j$), thì $i$ có thể đánh bại $j$ trong trận đánh, và $j$ được coi là bị loại.
• Nếu không, không có gì xảy ra.

Lưu ý rằng các cuộc chiến chỉ là tưởng tượng; nghĩa là một sinh vật bị loại không thể tham gia các trận đánh tiếp theo trong cùng cuộc chiến, nhưng nó sẽ hồi phục vào đầu cuộc chiến tiếp theo và có thể tham gia các trận đánh của những cuộc chiến sau.

Các sinh vật không ổn định và bị đột biến theo thời gian. Bạn được cho $q$ lần đột biến. Sau mỗi lần, thuộc tính của một sinh vật thay đổi. Cụ thể, trong lần đột biến thứ $i$, sinh vật thứ $v_i$ có sức tấn công được cập nhật thành $x_i$ và sức phòng thủ thành $y_i$. Các đột biến có tác dụng lâu dài: sau lần đột biến thứ $i$, ảnh hưởng của $i-1$ lần đột biến đầu tiên vẫn được tích lũy.

Vì mỗi sinh vật còn lại đều tiếp tục đe dọa những bông hoa, bạn muốn tìm số sinh vật ít nhất có thể còn lại sau một chuỗi tối ưu trong một cuộc chiến tưởng tượng. Bạn cần trả lời cho mọi trạng thái trước tất cả các đột biến và sau mỗi lần đột biến.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $q$ ($1 \le n \le 4 \cdot 10^5$, $0 \le q \le 4 \cdot 10^5$), trong đó $n$ là số sinh vật và $q$ là số lần đột biến.

$n$ dòng tiếp theo mô tả tất cả các sinh vật. Dòng thứ $i$ trong số đó chứa hai số nguyên $a_i$ và $b_i$ ($1 \le a_i,b_i \le 10^9$), trong đó $a_i$ là sức tấn công và $b_i$ là sức phòng thủ của sinh vật thứ $i$.

$q$ dòng tiếp theo mô tả tất cả các lần đột biến. Dòng thứ $i$ trong số đó chứa ba số nguyên $v_i$, $x_i$ và $y_i$ ($1 \le v_i \le n$, $1 \le x_i,y_i \le 10^9$), trong đó $x_i$ là sức tấn công mới của sinh vật $v_i$ và $y_i$ là sức phòng thủ mới của sinh vật $v_i$.

Dữ liệu ra

In $q+1$ dòng, mỗi dòng chứa một số nguyên, lần lượt là đáp án trước khi có bất kỳ đột biến nào và sau mỗi lần đột biến.

Ví dụ

Dữ liệu vào 1

3 1
1 1
2 2
3 3
2 2 4

Dữ liệu ra 1

1
2

Ghi chú

Trong ví dụ, trước khi đột biến bắt đầu, sinh vật thứ ba có thể đánh bại sinh vật thứ nhất và thứ hai. Rõ ràng đây là chuỗi trận đánh tưởng tượng tối ưu, nên đáp án là $1$.

Sau lần đột biến đầu tiên, sức tấn công của sinh vật thứ hai trở thành $2$ và sức phòng thủ trở thành $4$. Lúc này sinh vật thứ ba chỉ có thể đánh bại sinh vật thứ nhất, còn lại $2$ sinh vật. Có thể chứng minh không có phương án tốt hơn, nên đáp án là $2$.