ในสวนอาซาเลียอันเงียบสงบ มีสิ่งมีชีวิตอันตราย $n$ ตัวปรากฏขึ้น สิ่งมีชีวิตแต่ละตัวมีพลังโจมตีและพลังป้องกัน เริ่มแรก สิ่งมีชีวิตตัวที่ $i$ ($1 \le i \le n$) มีพลังโจมตี $a_i$ และพลังป้องกัน $b_i$

คุณเป็นผู้พิทักษ์สวนอาซาเลีย และสามารถจินตนาการถึงสงครามระหว่างพวกมันได้ สงครามหนึ่งครั้งประกอบด้วยการต่อสู้หลายครั้ง (อาจเป็น $0$ ครั้ง) ในการต่อสู้ในจินตนาการแต่ละครั้ง คุณเลือกสิ่งมีชีวิตที่ยังมีชีวิตอยู่สองตัว $i$ และ $j$ ($1 \le i,j \le n$, $i \ne j$) แล้ว:

• หากพลังโจมตีของสิ่งมีชีวิต $i$ มากกว่าหรือเท่ากับพลังป้องกันของสิ่งมีชีวิต $j$ (นั่นคือ $a_i \ge b_j$) แล้ว $i$ สามารถเอาชนะ $j$ ในการต่อสู้ได้ และถือว่า $j$ ถูกกำจัด
• มิฉะนั้น จะไม่มีอะไรเกิดขึ้น

โปรดสังเกตว่าสงครามเป็นเพียงจินตนาการ กล่าวคือ สิ่งมีชีวิตที่ถูกกำจัดไม่สามารถเข้าร่วมการต่อสู้ต่อไปในสงครามเดียวกันได้ แต่จะฟื้นพลังเมื่อสงครามครั้งถัดไปเริ่มขึ้น จึงสามารถเข้าร่วมการต่อสู้ในสงครามครั้งต่อ ๆ ไปได้

สิ่งมีชีวิตเหล่านี้ไม่เสถียรและกลายพันธุ์ตามเวลา กำหนดการกลายพันธุ์ $q$ ครั้งให้คุณ หลังแต่ละครั้ง คุณสมบัติของสิ่งมีชีวิตหนึ่งตัวจะเปลี่ยนไป โดยในการกลายพันธุ์ครั้งที่ $i$ พลังโจมตีของสิ่งมีชีวิตตัวที่ $v_i$ จะเปลี่ยนเป็น $x_i$ และพลังป้องกันจะเปลี่ยนเป็น $y_i$ การกลายพันธุ์มีผลถาวร กล่าวคือ หลังการกลายพันธุ์ครั้งที่ $i$ ผลของการกลายพันธุ์ $i-1$ ครั้งแรกยังคงสะสมอยู่

เนื่องจากสิ่งมีชีวิตทุกตัวที่เหลือยังคงเป็นภัยต่อดอกไม้ คุณต้องการหาจำนวนสิ่งมีชีวิตที่เหลือน้อยที่สุดหลังจากเลือกลำดับการต่อสู้ที่ดีที่สุดในสงครามในจินตนาการ คุณต้องตอบสำหรับทุกสถานะก่อนการกลายพันธุ์ทั้งหมดและหลังการกลายพันธุ์แต่ละครั้ง

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็มสองจำนวน $n$ และ $q$ ($1 \le n \le 4 \cdot 10^5$, $0 \le q \le 4 \cdot 10^5$) โดย $n$ คือจำนวนสิ่งมีชีวิต และ $q$ คือจำนวนครั้งของการกลายพันธุ์

$n$ บรรทัดถัดไปอธิบายสิ่งมีชีวิตทั้งหมด บรรทัดที่ $i$ ในส่วนนี้มีจำนวนเต็มสองจำนวน $a_i$ และ $b_i$ ($1 \le a_i,b_i \le 10^9$) โดย $a_i$ คือพลังโจมตี และ $b_i$ คือพลังป้องกันของสิ่งมีชีวิตตัวที่ $i$

$q$ บรรทัดถัดไปอธิบายการกลายพันธุ์ทั้งหมด บรรทัดที่ $i$ ในส่วนนี้มีจำนวนเต็มสามจำนวน $v_i$, $x_i$ และ $y_i$ ($1 \le v_i \le n$, $1 \le x_i,y_i \le 10^9$) โดย $x_i$ คือพลังโจมตีใหม่ของสิ่งมีชีวิต $v_i$ และ $y_i$ คือพลังป้องกันใหม่ของสิ่งมีชีวิต $v_i$

ข้อมูลส่งออก

แสดงผล $q+1$ บรรทัด แต่ละบรรทัดมีจำนวนเต็มหนึ่งจำนวน เป็นคำตอบก่อนเกิดการกลายพันธุ์ใด ๆ และหลังการกลายพันธุ์แต่ละครั้งตามลำดับ

ตัวอย่าง

ข้อมูลนำเข้า 1

3 1
1 1
2 2
3 3
2 2 4

ข้อมูลส่งออก 1

1
2

หมายเหตุ

ในตัวอย่าง ก่อนเริ่มการกลายพันธุ์ สิ่งมีชีวิตตัวที่สามสามารถเอาชนะตัวที่หนึ่งและตัวที่สองได้ เห็นได้ชัดว่านี่คือลำดับการต่อสู้ในจินตนาการที่ดีที่สุด ดังนั้นคำตอบคือ $1$

หลังการกลายพันธุ์ครั้งแรก พลังโจมตีของสิ่งมีชีวิตตัวที่สองกลายเป็น $2$ และพลังป้องกันกลายเป็น $4$ ตอนนี้สิ่งมีชีวิตตัวที่สามเอาชนะได้เพียงตัวที่หนึ่ง จึงเหลือสิ่งมีชีวิต $2$ ตัว สามารถพิสูจน์ได้ว่าไม่มีวิธีที่ดีกว่านี้ ดังนั้นคำตอบคือ $2$