Cho một biểu thức số học gồm ~n~ toán hạng liên kết bởi ~n - 1~ phép toán xen kẽ giữa chúng. Mỗi toán hạng là số nguyên dương không vượt quá ~S~. Có ~k~ loại phép toán, được đánh số từ ~1~ đến ~k~. Phép toán ~i~ (kí hiệu ~(op)_i~) có độ ưu tiên ~p_i~ ~(1 \le p_i \le k)~. Nếu các phép toán có độ ưu tiên khác nhau, thì phép toán có độ ưu tiên cao hơn sẽ được thực hiện trước. Nếu tất cả các phép toán có cùng độ ưu tiên, chúng được thực hiện từ trái sang phải. Trong biểu thức có dấu ngoặc, các phép toán trong ngoặc được thực hiện trước.

Mỗi phép toán được định nghĩa bởi một danh sách các bộ ba ~(x, y, z)~, nghĩa là nếu áp dụng phép toán ~i~ với toán hạng trái là ~x~ và toán hạng phải là ~y~, ta nhận được kết quả ~z~ (kí hiệu: ~x (op)_i y = z~). Lưu ý rằng ~x (op)_i y = z~ không đảm bảo ~y (op)_i x = z~, nghĩa là các phép toán không nhất thiết có tính chất giao hoán. Với mỗi cặp ~(x, y)~ chỉ có tối đa một kết quả. Nếu tại một bước tính ~x (op) y~, phép toán ~(op)~ không có định nghĩa cho cặp ~(x, y)~, thì biểu thức trở nên vô nghĩa.

Yêu cầu: Tìm số lượng dấu cặp ngoặc tối thiểu cần đặt vào biểu thức để giá trị biểu thức bằng mỗi giá trị từ ~1~ đến ~S~. Nếu không thể đạt được một giá trị nào đó, in ra ~-1~.

Input

• Dòng 1: ba số nguyên ~n, k, S~ ~(1 \le n, k, S \le 100)~.

• Dòng 2: ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le S)~.

• Dòng 3: ~n - 1~ số nguyên ~b_1, b_2, \dots, b_{n-1}~ ~(1 \le b_i \le k)~, ~b_i~ là phép toán giữa ~a_i~ và ~a_{i+1}~.

• Tiếp theo là ~k~ nhóm dòng mô tả các phép toán, nhóm dòng ~i~ gồm:

  • Dòng đầu tiên chứa hai số nguyên ~t_i, p_i~, ~t_i~ là số bộ ba định nghĩa phép toán ~(op)_i~.

  • Sau đó là ~t_i~ dòng, mỗi dòng gồm ba số nguyên ~x, y, z~ ~(1 \le x, y, z \le S)~ mô tả ~x (op)_i y = z~.

Tổng số bộ ba định nghĩa của tất cả phép toán không vượt quá ~200~.

Output

• Dòng 1: ~S~ số nguyên, số thứ ~i~ ~(1 \le i \le S)~ là số dấu ngoặc tối thiểu cần thêm để biểu thức có giá trị bằng ~i~, nếu không tồn tại biểu thức cho kết quả bằng ~i~ thì số này bằng ~-1~.

Scoring

Sample Input 1

6 1 4
4 1 3 2 1 4
1 1 1 1 1
7 1
4 2 1
3 3 4
3 2 4
1 4 3
4 1 3
1 3 2
3 4 4

Sample Output 1

-1 1 2 1

Notes

Ký hiệu ~\oplus~ là phép toán có ~7~ quy tắc tính: ~4 \oplus 2 = 1; 3 \oplus 3 = 4; 3 \oplus 2 = 4; 1 \oplus 4 = 3; 4 \oplus 1 = 3; 1 \oplus 3 = 2; 3 \oplus 4 = 4~.

Dãy toán hạng ~(4,1,3,2,1,4)~ không thể tạo được kết quả bằng ~1~.

Các kết quả ~2, 3, 4~ đạt được bằng các biểu thức:

• ~4 \oplus 1 \oplus 3 \oplus 2 \oplus (1 \oplus 4) = 4 \oplus 1 \oplus 3 \oplus 2 \oplus 3 = 3 \oplus 3 \oplus 2 \oplus 3 = 4 \oplus 2 \oplus 3 = 1 \oplus 3 = 2~

• ~4 \oplus (1 \oplus (3 \oplus 2 \oplus 1)) \oplus 4 = 4 \oplus (1 \oplus (4 \oplus 1)) \oplus 4 = 4 \oplus (1 \oplus 3) \oplus 4 = 4 \oplus 2 \oplus 4 = 1 \oplus 4 = 3~

• ~4 \oplus 1 \oplus (3 \oplus 2) \oplus 1 \oplus 4 = 4 \oplus 1 \oplus 4 \oplus 1 \oplus 4 = 3 \oplus 4 \oplus 1 \oplus 4 = 4 \oplus 1 \oplus 4 = 3 \oplus 4 = 4~