Тыныш азалия бағында $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$.