402200: GYM100694 J Ticket Booking

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Ticket Bookingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The biggest student ACM (Anarchy Code Modification) contest will be held in N-sk city soon. Slava is the leader of the group of students who will take part in this competition, so he must buy the train tickets for all members of the group. Each student told him his favourite seat number where this student wants to travel (all numbers are distinct).

Ticket window workers have gone on strike, so Slava has to use the terminal. The process of buying tickets in the terminal goes this way:

  1. The personal data of the passengers is entered. The maximum number of people whose information can be entered at one terminal usage is k.
  2. The lower and upper bounds of the seat numbers are entered. This segment can contain the seats that have been already bought. First c free seats in this segment are booked, where c is the number of people whose information has been filled at the previous step. If the segment doesn't contain enough free seats, the booking isn't performed.

Every terminal usage is accompanied by the entering of the great amount of information, so Slava wants to minimize the number of usages. He can't determine the optimal order by himself — the last bus to his home is about to leave — so you should help him.

Input

The first line contains three space-separated integers n, m and k (1 ≤ n, m, k ≤ 105, n ≤ m) — the number of students in the group, the number of free seats and the maximal number of people at one terminal usage.

The second line contains n distinct integers wi (1 ≤ wi ≤ 109) — the seat number preferred by the i-th student. They are sorted in ascending order.

The third line contains m distinct integers fj (1 ≤ fj ≤ 109) — the numbers of free seats. They are also sorted in ascending order.

It's guaranteed that every student wants to travel at a free seat. That is, for each 1 ≤ i ≤ n there exists such 1 ≤ j ≤ m that wi = fj.

Output

In the first line write a single integer s — the minimal number of terminal usages.

In each of the next s lines write the information about terminal usages — the number of people and their numbers, separated by spaces. Each student should be presented in only one terminal usage. The tickets should be bought for all students in the group.

ExamplesInput
4 6 2
1 4 5 6
1 2 4 5 6 8
Output
3
1 1
2 2 3
1 4
Input
12 21 4
2 6 8 10 12 28 40 44 46 48 50 52
2 4 6 8 10 12 24 26 28 30 32 33 34 35 36 40 44 46 48 50 52
Output
5
1 1
4 2 3 4 5
1 6
4 7 8 9 10
2 11 12

加入题单

上一题 下一题 算法标签: