Lịch phát tín hiệu định kỳ

Bối cảnh và bài toán

Một trung tâm giám sát vận hành nhiều tác vụ định kỳ. Mỗi tác vụ có một id duy nhất và một chu kỳ period. Hệ thống bắt đầu tại thời điểm 0; tác vụ có chu kỳ period sẽ phát tín hiệu lần đầu tại thời điểm period, sau đó tiếp tục phát sau mỗi period đơn vị thời gian.

Bộ phận vận hành cần biết k tín hiệu đầu tiên mà hệ thống sẽ xử lý. Nếu nhiều tác vụ phát tín hiệu tại cùng một thời điểm, tác vụ có id nhỏ hơn được xử lý trước.

Yêu cầu

In id của k lần phát tín hiệu đầu tiên theo đúng thứ tự xử lý.

Input

• Dòng 1: số tác vụ n.
• n dòng tiếp theo: hai số nguyên id period mô tả một tác vụ.
• Dòng cuối: số nguyên k.

Output

In k dòng. Mỗi dòng chứa id của tác vụ được xử lý ở lần tiếp theo.

Ràng buộc

• 1 <= n <= 5 * 10^4
• 1 <= k <= 10^5
• 1 <= id, period <= 10^9
• Các id đôi một khác nhau.

Chấm điểm

Ví dụ 1

Input

2
2004 200
2005 300
5

Output

2004
2005
2004
2004
2005

Giải thích. Tác vụ 2004 phát ở các thời điểm 200, 400, 600, ...; tác vụ 2005 phát ở 300, 600, 900, .... Tại thời điểm 600 hai tác vụ cùng đến hạn nên id = 2004 được xử lý trước.

Ví dụ 2

Input

3
8 5
3 5
20 2
6

Output

20
20
3
8
20
20

Giải thích. Hai tác vụ 3 và 8 cùng đến hạn tại thời điểm 5, vì vậy tác vụ 3 đứng trước do có id nhỏ hơn.

Thông tin bài tập

Nguồn: Phỏng theo UVa Online Judge 1203 — Argus. Statement, bối cảnh, input và constraints đã được biên tập lại cho FULLHOUSE DEV.