Một bãi đỗ xe gần Vạn Lý Trường Thành có một hàng dài các chỗ đỗ, với một đầu được gọi là bên trái và đầu kia là bên phải. Tất cả các chỗ đều có xe. Mỗi xe thuộc một loại được biểu diễn bằng một số nguyên; nhiều xe có thể cùng loại. Các công nhân muốn sắp xếp xe theo thứ tự loại không giảm từ trái sang phải.

Việc sắp xếp được thực hiện qua các lượt. Trong một lượt, mỗi công nhân có thể đồng thời lái một xe ra khỏi chỗ đỗ, rồi đỗ xe đó vào một chỗ mà một xe đã rời đi trong chính lượt ấy. Một số công nhân có thể không di chuyển xe trong một lượt. Để làm việc hiệu quả, số lượt nên nhỏ.

Gọi \(N\) là số xe và \(W\) là số công nhân. Cho các loại xe theo thứ tự ban đầu và số công nhân, hãy tìm cách sắp xếp sử dụng không quá \(\left\lceil N/(W-1)\right\rceil\) lượt, tức là \(N/(W-1)\) làm tròn lên. Số lượt ít nhất cần thiết không bao giờ vượt quá giới hạn này.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(N\), \(M\), \(W\): số xe, số loại xe và số công nhân. Các giới hạn là \(2 \le N \le 20000\), \(2 \le M \le 50\) và \(2 \le W \le M\). Các loại được đánh số từ \(1\) đến \(M\), và mỗi loại có ít nhất một xe.

Dòng thứ hai chứa \(N\) số nguyên; số thứ \(i\) là loại của xe ở vị trí thứ \(i\) tính từ trái sang phải.

Dữ liệu ra

Dòng đầu chứa số nguyên \(R\), số lượt trong phương án. Tiếp theo là \(R\) dòng mô tả các lượt từ \(1\) đến \(R\). Mỗi dòng bắt đầu bằng số xe \(C\) được di chuyển trong lượt đó, tiếp theo là \(2C\) số nguyên chia thành \(C\) cặp. Mỗi cặp mô tả một xe: số đầu là vị trí trước lượt di chuyển, số sau là vị trí sau lượt di chuyển. Các vị trí được đánh số từ \(1\) đến \(N\) từ trái sang phải. Chỉ cần in một phương án hợp lệ nếu có nhiều phương án.

Chấm điểm

Đặt \(Q=\left\lceil N/(W-1)\right\rceil\). Nếu mô tả \(R\) lượt không hợp lệ hoặc không đưa các xe về đúng thứ tự yêu cầu, điểm của lần chạy đó là \(0\). Ngược lại, điểm được tính theo tỷ lệ của điểm tối đa cho lần chạy:

Ví dụ

10 4 4
2 3 3 4 4 2 1 1 3 1

3
4 2 7 3 8 7 2 8 3
3 4 9 9 6 6 4
3 1 5 5 10 10 1

2 1 1 4 4 2 3 3 3 1
2 1 1 2 4 3 3 3 4 1
1 1 1 2 2 3 3 3 4 4