Ride-Sharing Service: Efficient Batching

Split all requests into as few groups as possible, where each group has at most 3 requests, the same exact pickup location, and a difference of at most 10 minutes between the latest and earliest times. Each request appears in exactly one group. IDs within each group are in ascending order; groups are ordered by the smallest original input index of their requests, ascending. When multiple optimal solutions exist, any of them is accepted.

This site has made the standard input and output explicit.

输入格式

The first line contains n, followed by two lines per request: the first line is id HH:MM and the second line is the full location name. 1≤n≤10000; on this site IDs are distinct integers in 1..10⁹, locations are 1..100 printable ASCII characters or spaces, and times are in 00:00..23:59.

输出格式

The first line is the number of groups B, followed by B lines, each giving the group size and then the group's IDs in ascending order.

样例 1

输入：

3
4 10:00
Main Gate
1 10:10
Main Gate
3 10:20
Main Gate

输出：

2
1 4
2 1 3

样例 2

输入：

4
8 00:00
A
2 00:00
A
5 00:00
A
1 00:00
A

输出：

2
1 8
3 1 2 5

样例 3

输入：

2
10 00:00
A
11 00:00
B

输出：

2
1 10
1 11

样例说明

Example 1: at least 2 groups are needed. IDs 1 and 4 can share a group with ID 3 alone, or ID 4 can be alone with IDs 1 and 3 together. Example 2: four compatible requests still need at least 2 groups because each group holds at most 3; any two-group split in the required order is accepted. Example 3: different locations cannot be grouped, so 2 groups are needed, in the order 10 then 11.