P15353 [COCI 2025/2026 #4] Ice Cream / Sladoled

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?

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 $q$ lines. Each line contains one positive integer, representing the answer.

### 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 | Subtask ID | Full Score | Constraints | | :-: | :-: | :- | | $1$ | $16$ | $n=1,q\le 20$ | | $2$ | $33$ | $q\le 100$ | | $3$ | $61$ | No additional constraints. | Translated by ChatGPT 5