Có \(n\) quầy kem, ban đầu không quầy nào có viên kem. Trong \(q\) ngày, ngày thứ \(i\) nhận cặp \((a,b)\): quầy \(a\) nhận một vị kem có giá trị \(b\). Tại mỗi quầy, một tổ hợp dùng ít nhất một viên kem đang có, mỗi loại được phép dùng không giới hạn lần. Giá trị tổ hợp là tổng các giá trị vị kem; chỉ xét giá trị không vượt quá \(50000\). Sau mỗi ngày, hãy in số giá trị khác nhau có thể tạo tại đúng quầy vừa nhận hàng.

Dữ liệu vào

Dòng đầu chứa \(n,q\) (\(1\le n\le100\), \(1\le q\le10^5\)). Mỗi trong \(q\) dòng tiếp theo chứa \(a,b\) (\(1\le a\le n\), \(1\le b\le50000\)).

Dữ liệu ra

In \(q\) dòng, là đáp án sau từng ngày.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(16\) điểm: \(n=1\), \(q\le20\).
2. \(33\) điểm: \(q\le100\).
3. \(61\) điểm: không có ràng buộc thêm.

Ví dụ

1 2
1 3
1 5

16666
49996

2 4
2 35625
1 25139
1 37795
2 17791

1
1
2
3

Nguồn

COCI 2025/2026 - Vòng 4, bài Sladoled.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.