Problem Description

There are $n$ sets $S_1\sim S_n$, all initially empty.

There are $q$ operations. In each operation, given positive integers $a,b$, it means setting $S_a\gets S_a\cup \{b\}$, and then you need to answer the following question:

• Assume every number in $S_a$ can be used an unlimited number of times. By selecting some numbers from $S_a$ (at least $1$ number) and adding them up, how many positive integers in $1\sim 50000$ can be obtained?

Input Format

The first line contains two positive integers $n,q$ ($1\le n\le 100$, $1\le q\le 10^5$).

The next $q$ lines each contain two positive integers $a,b$ ($1\le a\le n$, $1\le b\le 50000$), describing one operation.

Output Format

Output $q$ lines. Each line contains one positive integer, representing the answer.

1 2
1 3
1 5

16666
49996

2 4
2 35625
1 25139
1 37795
2 17791

1
1
2
3

Hint

Sample Explanation

Explanation for sample 1:

• After the first operation, you can obtain multiples of $3$. Among those not greater than $50000$, there are $16666$.
• After the second operation, the only numbers that cannot be obtained are $1,2,4,7$.

Subtasks

Translated by ChatGPT 5