Examination Material

The book for a certain course in the second class of senior high school has 10 chapters, numbered from 1 to 10. The material for the exams consists of 4 out of these 10 chapters.

One way to determine the material is to follow two steps: in the first step, a subset S of k (4 ~<~ k ~<~ 7) chapters is chosen from the 10. Then, in the second step, 4 chapters are selected from S, constituting the material for the course.

The selection of chapters in the first step is based on the importance of each chapter. The teacher, who determines the course material, has assigned a weight coefficient to each chapter based on certain criteria. In other words, a set of ten pairs is given, each consisting of the chapter number and its corresponding weight coefficient.

The task is to write a program that, given the ten chapters with their coefficients and the number ~k~, records all possible combinations of chapters that the teacher can use to determine the course material. Specifically, all possible combinations of k elements (chapters from the book) in groups of 4 are requested. The weight coefficients are designed to allow the selection of exactly k elements in subset S.

For example, if we have the pairs {(1,18), (2,16), (3,17), (4,5), (5,17), (6,4), (7,3), (8,17), (9,6), (10,4)} for k=5, we have S = 1,2,3,5,8, and there are 5 possible ways to determine the material: [1,2,3,5], [1,2,3,8], [1,2,5,8], [1,3,5,8], [2,3,5,8].

Input

The input starts with the number k on the first line. In the following lines, the 10 chapters are given along with their corresponding weight coefficients. Each pair consists of a chapter number and its respective weight coefficient. Each pair is on a separate line, and there is exactly one space between the chapter number and its weight coefficient.

Output

The output starts with the subset S on the first line, that will determine the subject matter, i.e., the k chapters (4 ~<~ k ~<~ 7) with the highest weight. In the following lines, the possible ways of determining the subject matter are given, i.e., the possible quadruples. Each quadruple is on a separate line, and the chapter numbers that constitute it are separated by spaces. The last line of the output file provides the number of different ways (quadruples) to determine the subject matter. Both the set S and the chapter numbers in each quadruple must be sorted lexicographically, i.e., first the smallest number, then the next largest, and so on. The different quadruples must also be in lexicographic order, as shown in the example below.

Examples of Input - Output Files:

STDIN (INPUT.TXT)

5
1 18
2 16
3 17
4 5
5 17
6 4
7 3
8 17
9 6
10 4

STDOUT (OUTPUT.TXT)

1 2 3 5 8
1 2 3 5
1 2 3 8
1 2 5 8
1 3 5 8
2 3 5 8
5

Note:

The executable file to be created should be named exams.exe.

ATTENTION! You must strictly adhere to the names and structure of the files; otherwise, your answer will be considered incorrect during evaluation.