Sau tất cả, Koruto muốn tránh mặt cô ấy càng nhiều càng tốt. Nhưng khổ nỗi cả hai lại học chung lớp, nên mỗi ngày vẫn phải di chuyển giữa cùng các tiết học.

Trong một ngày có \(n\) tiết học. Tiết học thứ \(i\) diễn ra ở phòng \(a_i\). Giữa các phòng có các hành lang hai chiều. Với mỗi cặp tiết liên tiếp \(i\) và \(i+1\), bạn được biết trước lộ trình mà cô ấy sẽ đi từ phòng \(a_i\) đến phòng \(a_{i+1}\).

Koruto muốn đi từ phòng \(a_i\) đến phòng \(a_{i+1}\) trong đúng cùng số bước với lộ trình đó, nhưng không được gặp cô ấy giữa đường.

Cụ thể, xét một lộ trình của cô ấy gồm \(L_i\) phòng:

với \(p_1 = a_i\) và \(p_{L_i} = a_{i+1}\). Cô ấy xuất phát tại \(p_1\) ở thời điểm \(0\), sau mỗi giây phải đi qua đúng một hành lang sang một phòng kề, và đến \(p_j\) ở thời điểm \(j-1\). Koruto cũng xuất phát cùng lúc ở \(p_1\), cũng phải di chuyển qua đúng một hành lang sau mỗi giây, không được đứng yên, và phải đến \(p_{L_i}\) sau đúng \(L_i - 1\) giây.

Koruto được xem là tránh được cô ấy nếu tại mọi thời điểm nguyên \(t\) thỏa mãn \(0 < t < L_i - 1\), hai người không ở cùng một phòng. Việc cùng ở phòng xuất phát tại \(t = 0\) và cùng đến phòng đích tại \(t = L_i - 1\) được cho phép.

Hãy cho biết với từng cặp tiết liên tiếp, Koruto có thể chọn một lộ trình an toàn hay không.

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(m\) lần lượt là số tiết học và số phòng.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) là phòng học của từng tiết.
• Dòng thứ ba chứa số nguyên \(k\) là số hành lang.
• \(k\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) cho biết có hành lang hai chiều nối hai phòng \(u\) và \(v\).
• Sau đó là \(n-1\) nhóm dòng. Nhóm thứ \(i\) mô tả lộ trình của cô ấy từ \(a_i\) đến \(a_{i+1}\):
  • Dòng đầu chứa số nguyên \(L_i\).
  • Dòng tiếp theo chứa \(L_i\) số nguyên \(p_1, p_2, \dots, p_{L_i}\).

Output

• In ra \(n-1\) dòng. Dòng thứ \(i\) in YES nếu Koruto có thể đi an toàn từ \(a_i\) đến \(a_{i+1}\), ngược lại in NO.

Constraints

• \(2 \le n \le 5000\)
• \(1 \le m \le 5000\)
• \(0 \le k \le 5000\)
• \(1 \le a_i \le m\)
• \(1 \le u, v \le m, u \neq v\)
• Không có hai hành lang trùng nhau.
• \(1 \le L_i\)
• Tổng tất cả \(L_i\) không vượt quá \(5000\).
• Với mỗi lộ trình \(p_1, \dots, p_{L_i}\):
  • \(p_1 = a_i\) và \(p_{L_i} = a_{i+1}\).
  • Hai phòng liên tiếp luôn có hành lang nối trực tiếp.
  • Các phòng trong cùng một lộ trình là đôi một khác nhau, tức lộ trình của cô ấy là một đường đi đơn.

Example

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

YES
NO

Subtasks

• Subtask 1 (30%): \(n, m, k\) và tổng \(L_i\) không vượt quá \(100\).
• Subtask 2 (30%): \(L_i \le 3\) với mọi \(i\).
• Subtask 3 (40%): Không có ràng buộc gì thêm ngoài ràng buộc chính.