평화로운 진달래 정원에 $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$는 $i$번째 생명체의 공격력이고 $b_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$입니다.