该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P15353 [COCI 2025/2026 #4] 冰激凌 / Sladoled

本题110分

题目描述

有 $n$ 个集合 $S_1\sim S_n$，初始全为空。

$q$ 次操作，每次操作给定正整数 $a,b$，表示令 $S_a\gets S_a\cup \{b\}$，然后求出如下问题的答案：

• 假设 $S_a$ 中每个数可以用无数次，选取若干个（至少 $1$ 个）$S_a$ 中的数相加，可以得到 $1\sim 50000$ 中的多少个正整数？

输入格式

第一行，两个正整数 $n,q$（$1\le n\le 100$，$1\le q\le 10^5$）。

接下来 $q$ 行，每行两个正整数 $a,b$（$1\le a\le n$，$1\le b\le 50000$），描述一次操作。

输出格式

输出 $q$ 行，每行一个正整数，表示答案。

输入输出样例 #1

输入 #1

1 2
1 3
1 5

输出 #1

16666
49996

输入输出样例 #2

输入 #2

2 4
2 35625
1 25139
1 37795
2 17791

输出 #2

1
1
2
3

说明/提示

样例解释

样例一解释：

• 第一次操作后，可以得到 $3$ 的倍数，不大于 $50000$ 的有 $16666$ 个。
• 第二次操作后，不能得到的数只有 $1,2,4,7$。

子任务