Trong 1 buổi học lập trình nâng cao của thầy Youtuber_TWK, vì quá chán với cách dạy của thầy nên doangiaphuc13 và bomao quyết định lẻn ra khỏi lớp. Nào ngờ, vừa ra tới cửa thì gặp ngay thầy giám thị KimHieu đang chờ sẵng. Thầy KimHieu quyết định sẽ phạt doangiaphuc13 và bomao bằng cách ra 1 bài tập về đồ thị để coi doangiaphuc13 và bomao đã hiểu bài chưa mà dám bỏ học, cụ thể đề bài như sau:
Thầy giám thị KimHieu cho doangiaphuc13 và bomao một đồ thị vô hướng liên thông gồm \(N\) đỉnh và \(M\) cạnh (\(N, M \le 10^5\)), đảm bảo đồ thị là một cactus (mỗi cạnh thuộc tối đa một chu trình đơn). Mỗi đỉnh \(u\) được gán một đa thức:

Với bậc tối đa \(2^K - 1\) (\(K \le 4\)). Định nghĩa đa thức của một đường đi đơn là tích chập XOR (XOR convolution) của tất cả các đa thức tại các đỉnh thuộc đường đi đó. Với mỗi cặp đỉnh \((u, v)\), ta định nghĩa đa thức tổng hợp là tổng các đa thức của tất cả các đường đi đơn từ \(u\) đến \(v\). doangiaphuc13 và bomao cần xử lý \(Q\) truy vấn (\(Q \le 10^5\)) gồm 2 loại:

1. \(1, u, c_0, c_1, ... c_{2^K-1}\): Cập nhật đa thức tại đỉnh \(u\) với các hệ số mới.
2. \(2, u, v, k\): Tính hệ số thứ \(k\) (\(0 \le k < 2^K\)) của đa thức tổng hợp giữa hai đỉnh \(u\) và \(v\), kết quả lấy modulo \(998244353\).

Nhưng vì bài quá khó nên doangiaphuc13 và bomao hoàn toàn không thể làm được vì vậy các bạn hãy giúp doangiaphuc13 và bomao tìm các hệ số theo như đề bài nhé!

Input

• Dòng đầu tiên gồm bốn số nguyên \(N, M, K, Q\).
• \(M\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u, v\) mô tả cạnh vô hướng của đồ thị.
• \(N\) dòng tiếp theo, mỗi dòng gồm \(2^K\) số nguyên mô tả các hệ số của đa thức khởi tạo cho các đỉnh từ \(1\) đến \(N\).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng của 2 loại đã nêu.

Constraints

• \(1 \le N, M, Q \le 10^5\)
• \(1 \le K \le 4\)
• Các hệ số của đa thức nằm trong khoảng \([0, 998244353 - 1]\).

Output

• Với mỗi truy vấn loại 2, in ra hệ số cần tìm trên một dòng.

Example

3 3 1 2
1 2
2 3
3 1
1 0
0 1
1 1
2 1 3 1
2 1 2 0

2
1

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

1
0

Scoring

• Subtask 1 (15% số điểm): \(N, M, Q \le 100, K = 1\), đồ thị là cây.
• Subtask 2 (35% số điểm): Đồ thị tổng quát dạng cactus nhưng \(K = 1, N, M, Q \le 1000\).
• Subtask 3 (50% số điểm): Không giới hạn gì thêm (\(N, M, Q \le 10^5, K \le 4\)).