Trong buổi phỏng vấn xin việc vào vị trí kiến trúc sư mạng, bộ phận tuyển dụng đưa cho bạn câu hỏi như sau:

Hệ thống máy tính của công ty gồm \(n\) máy tính, máy thứ \(i\) (\(1 \leq i \leq n\)) có \(c_i\) cổng kết nối. Các máy tính được chia thành \(k\) trạm, trạm thứ \(j\) (\(1 \leq j \leq k\)) có \(x_j\) máy tính, mỗi máy tính thuộc đúng một trạm.

Có \(m\) yêu cầu dạng \((u,v)\): Mỗi máy trong trạm \(u\) muốn liên lạc với từng máy trong trạm \(v\). Ta cần thiết kế đường truyền tin giữa các trạm máy tính khác nhau, bằng cách thiết lập kết nối hai chiều giữa các cặp hai máy bất kì sao cho thỏa mãn \(m\) yêu cầu trên và số kết nối của mỗi máy không được vượt quá số cổng kết nối của máy đó. Biết rằng để máy này truyền được tin tới máy khác, có thể truyền trực tiếp hoặc gián tiếp qua một số máy trung gian nào đó.

Để đánh giá mức độ hiệu quả của mạng, người ta định nghĩa hàm \(f\):

• Giả sử tổng số kết nối là \(E\).
• Định nghĩa độ trễ mạng \(L\) như sau: xét cặp máy \((x,y)\) (\(x \neq y\)) bất kì, mà \(x\) có đường truyền đến \(y\). Đặt \(d(x,y)\) là đường truyền ngắn nhất (đi qua ít kết nối nhất) giữa hai máy này. Độ trễ \(L\) của hệ thống sẽ là \(\max(d(x,y))\) trong mọi cặp \((x,y)\) đó.
• Khi đó: \(f = E \cdot n + L\).

Hãy thiết kế một hệ thống mạng có \(f\) nhỏ nhất.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(k\) và \(m\) (\(1 \leq k \leq n \leq 10 ^ 5\), \(1 \leq m \leq \min(k^2, 10^5)\)) lần lượt là số máy, số trạm và số yêu cầu.
• Dòng tiếp theo chứa \(n\) số nguyên \(c_1, c_2, \ldots, c_n\) (\(2 \leq c_i \leq n\)) là số lượng cổng kết nối của mỗi máy.
• Tiếp theo là \(k\) nhóm dòng mô tả các trạm máy tính \(1,2,3,\ldots,k\):
  • Dòng đầu tiên chứa số nguyên \(x_j\) là số lượng máy của trạm thứ \(j\).
  • Dòng tiếp theo chứa \(x_j\) số nguyên là số hiệu của các máy.
  • Dữ liệu vào đảm bảo \(x_1 + x_2 + \ldots + x_k = n\) và số hiệu của mỗi máy khác nhau đôi một và tạo thành một hoán vị của \(\{1,2,3,\dots,n\}\).
• Trong \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) (\(1 \le u,v \le k\)) cho biết yêu cầu giữa hai trạm \(u\) và \(v\).

Output

• Dòng đầu tiên in ra số nguyên \(f\).
• Nếu \(E \leq 10^5\), in ra các cặp kết nối theo định dạng u v trong \(E\) dòng tiếp theo.

Nếu có nhiều cách nối khác nhau, bạn hãy in ra 1 cách nối bất kì. Chứng minh được luôn tồn tại cách nối các máy thỏa mãn các yêu cầu với giới hạn của đề bài.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 6\).
• Subtask \(2\) (\(30\%\) số điểm): \(c_i = n \ \forall 1 \leq i \leq n\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 3 2
3 3 3 
1
2
1
3
1
1
2 1
2 3

8
3 2
2 1

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

60 
1 2
2 5
2 3
3 4
3 6
6 8
6 7