A relay race has n legs, numbered 1 through n. As each runner finishes, a spotter phones the finish time for that runner's leg in to the broadcast booth — but spotters call in whenever their runner finishes, so leg times can arrive in any order, and each leg is called in exactly once over the course of the race.

The booth can only announce leg times in leg order: leg 1's time must be announced before leg 2's, leg 2's before leg 3's, and so on. Keep a marker at the next leg still awaiting announcement (it starts at leg 1). Every time a new leg time is phoned in, announce every leg time that this call-in newly makes announceable: starting at the marker, announce leg times for as long as consecutive legs already have a recorded time, then advance the marker past everything just announced. If the leg at the marker still has no recorded time, announce nothing for this call.

Input format

Line 1: an integer n — the total number of legs. Line 2: an integer q — the number of call-ins. Next q lines: each contains two integers id and time — leg id's finish time is time. Each id (1 <= id <= n) appears in exactly one call-in across the whole input.

Output format

q lines. The i-th line corresponds to the i-th call-in (in input order): print the leg times newly announced by that call-in, space-separated in leg order, or print an empty line if nothing becomes announceable yet.

Constraints

• 1 <= n <= 1000
• 1 <= q <= n
• 1 <= id <= n, and all ids are distinct across the q call-ins
• 1 <= time <= 10^9

5
5
3 300
1 100
2 200
5 500
4 400

100
200 300

400 500

3
3
1 10
2 20
3 30

10
20
30