레이팅 미적용In the ice cream city, \(n\) ice cream stands have opened, but at the opening, none
of the stands had any ice cream scoops for sale.
In the next \(q\) days, shipments of ice cream scoops will arrive at some stands. On
each of the \(q\) days, two integers \(a\) and \(b\) are given, meaning that stand \(a\) received
a shipment of ice cream scoops of flavor \(b\) on that day.
At each stand, it is also possible to make ice cream combinations. A combination
can use the scoops that are available at that stand, where each scoop can be
used an arbitrary number of times, and a combination consists of at least 1 ice
cream scoop.
The value of a combination is equal to the sum of the flavors of the scoops in that combination, and flavors
can repeat. We are interested in combinations whose value is less than or equal to 50000 (combinations
with higher values are too sweet).
After each day, it is necessary to print how many different values of ice cream combinations can be made
at the stand that received ice cream scoops on that day.
Subtask 1 (16 points): \(n = 1\), \(q \le 20\)
Subtask 2 (33 points): \(q \le 100\)
Subtask 5 (61 points): No additional constraints.
The first line contains the natural numbers \(n\) and \(q\) (\(1 \le n \le 100\), \(1 \le q \le 10^{5}\)), as described in the
problem statement.
Each of the next \(q\) lines contains two numbers \(a\) and \(b\) (\(1 \le a \le n\), \(1 \le b \le 50000\)), as described in the
problem statement.
Print \(q\) lines with the answers to the queries described in the problem statement.
1 2
1 3
1 516666
499962 4
2 35625
1 25139
1 37795
2 177911
1
2
3Explanation of the first sample test: After the first day, the values of ice cream combinations at
the first stand that can be made are all multiples of 3 less than or equal to 50000. There are 16666 such
combinations. After the second day, the only combination values that cannot be made are: 1, 2, 4, 7. All
other combination values can be made, totaling 49996.