School principal introduced a new system of duties to maintain order in all classrooms. Each student is assigned one classroom he is responsible for. Each day two students responsible for different classrooms should be on duty. These students should water the flowers in their classrooms and ensure that the highlighters in computer classrooms are not dry. The principal wants you to make a plan of the duties for the first m days of study. Each of the students should be on duty at least once during these days. You are to determine for each student the classroom he will be responsible for and the days this student will be on duty. Of course, each classroom should be assigned to at least one student. In addition to that, the principal requires that no pair of students should be on duty twice. To make your task easier, the principal allows you to distribute the duties unevenly — the students who misbehave will have more duties than those who are diligent.

The first line contains three space-separated integers: n — the number of students in the school, k — the number of classrooms, and m — the number of days in the required plan of duties. These numbers satisfy the constraint 2 ≤ k ≤ n ≤ 100. You may assume that there is at least one correct plan of the duties for given n, k and m.

Let the students be numbered from 1 to n, and the classrooms numbered from 1 to k. Output the assignments of the students to the classrooms on the first n lines: i-th line should contain the number of classroom i-th student is responsible for. The next m lines should contain the pairs of numbers of students who will be on duty on each of m days. Remember that these pairs should be unique, and the students who are responsible for the same classroom can't be paired.