Петрик і урок фізкультури

Limits: 1 sec., 256 MiB

Протягом деякого часу на уроки фізкультури до Петрика забігали та вибігали учні. Кожний учень мав унікальний зріст. Петрика зацікавили два питання:

1) Яким по рахунку буде учень, який щойно забіг на урок, якщо відсортувати всіх учнів у цей момент у порядку зростання

2) Скільки учнів залишилося на уроці зі зростом більшим, ніж в учня, який щойно покинув урок.

Допоможіть Петрику справитися із завданням.

Input

У першому рядку одне число \(H\) — зріст Петрика.

У наступному рядку одне число \(Q\) — скільки учнів забігало та вибігало з уроку фізкультури.

У наступних \(Q\) рядках два числа \(t\) та \(x\). Якщо \(t=1\) то учень зі зростом \(x\) забіг на урок фізкультури. Якщо \(t=2\) то учень зі зростом \(x\) покинув урок фізкультури.

Output

У \(Q\) рядках відповідь на перше або друге запитання.

Constraints

\(1 \le H \le 10^9\),

\(1 \le Q \le 10^5\),

\(1 \le t \le 2\),

\(1 \le x \le 10^9\),

усі учні, що заходили на урок мають різний зріст \(x\),

коли учень зі зростом \(x\) покидає урок, гарантується, що такий присутній на уроці.

Samples

Input (stdin) сopy	Output (stdout) сopy
1 5 1 2 1 4 1 3 2 2 1 5	2 3 3 2 4

Input (stdin) сopy	Output (stdout) сopy
10 5 1 2 2 2 1 15 2 15 1 11	1 1 2 0 2