Cho biểu thức gồm ~n~ toán hạng ~a_1,a_2,\dots,a_n~ và ~n-1~ phép toán ~b_1,b_2,\dots,b_{n-1}~, trong đó ~b_i~ là phép toán nằm giữa ~a_i~ và ~a_{i+1}~.

Có ~k~ loại phép toán, đánh số từ ~1~ đến ~k~. Phép toán ~i~ có độ ưu tiên ~p_i~. Độ ưu tiên lớn hơn thì được thực hiện trước. Nếu hai phép toán có cùng độ ưu tiên thì được thực hiện từ trái sang phải.

Mỗi phép toán là một phép toán nhị phân không nhất thiết giao hoán, được mô tả bằng các bộ ba ~x,y,z~, nghĩa là: ~x \operatorname{op}_i y = z~.

Với mỗi cặp ~x,y~, mỗi phép toán có nhiều nhất một kết quả. Nếu trong quá trình tính xuất hiện một cặp mà phép toán không được định nghĩa, biểu thức đó là vô nghĩa.

Yêu cầu

Với mỗi giá trị từ ~1~ đến ~S~, hãy tìm số cặp ngoặc tối thiểu cần thêm vào biểu thức để biểu thức có giá trị đó. Nếu không thể thu được giá trị ấy, in ra ~-1~.

Dữ liệu

Dòng ~1~ chứa ba số nguyên ~n,k,S~.

Dòng ~2~ chứa ~n~ số nguyên ~a_1,a_2,\dots,a_n~.

Dòng ~3~ chứa ~n-1~ số nguyên ~b_1,b_2,\dots,b_{n-1}~, trong đó ~b_i~ là phép toán giữa ~a_i~ và ~a_{i+1}~.

Tiếp theo là ~k~ nhóm mô tả các phép toán.

Với nhóm ~i~:

• Dòng đầu chứa hai số nguyên ~t_i,p_i~.
• ~t_i~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~x,y,z~, nghĩa là ~x \operatorname{op}_i y = z~.

Kết quả

In ra ~S~ số nguyên. Số thứ ~v~ là số cặp ngoặc tối thiểu để biểu thức có giá trị bằng ~v~, hoặc ~-1~ nếu không thể đạt được.

Ví dụ

Ví dụ 1

Input

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

Output

-1 1 2 1

Giải thích

Ví dụ 1

Ký hiệu ~\oplus~ là phép toán duy nhất, với các quy tắc:

~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~.

Không thể tạo giá trị ~1~.

Các giá trị còn lại đạt được như sau:

• Giá trị ~2~: ~4 \oplus 1 \oplus 3 \oplus 2 \oplus (1 \oplus 4)~.
• Giá trị ~3~: ~4 \oplus (1 \oplus ((3 \oplus 2) \oplus 1)) \oplus 4~.
• Giá trị ~4~: ~4 \oplus 1 \oplus (3 \oplus 2) \oplus 1 \oplus 4~.

Vì vậy đáp án là ~[-1,1,2,1]~.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le n,k,S \le 100~.

~1 \le a_i \le S~.

~1 \le b_i \le k~.

~1 \le p_i \le k~.

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

Chấm điểm

• Subtask ~1~: ~10\%~, kết quả cho mỗi giá trị chỉ có thể là ~0~ hoặc ~-1~.
• Subtask ~2~: ~10\%~, ~k=1~, kết quả cho mỗi giá trị chỉ có thể là ~0~, ~1~ hoặc ~-1~.
• Subtask ~3~: ~20\%~, ~k=1~.
• Subtask ~4~: ~60\%~, không có ràng buộc bổ sung.