Cập Nhật Đường Và Cây Con

Cho một cây gồm $n$ đỉnh, đánh số từ $1$ đến $n$. Cây được chọn gốc tại đỉnh $r$; vì vậy, khái niệm cây con trong bài luôn được hiểu theo gốc này. Mỗi đỉnh $i$ có một giá trị nguyên không âm ban đầu $a_i$.

Bạn cần xử lý lần lượt $m$ thao tác thuộc bốn loại:

• $1$ $x$ $y$ $z$: cộng $z$ vào giá trị của mọi đỉnh trên đường đơn từ $x$ đến $y$, kể cả hai đầu mút;
• $2$ $x$ $y$: tính tổng giá trị của mọi đỉnh trên đường đơn từ $x$ đến $y$;
• $3$ $x$ $z$: cộng $z$ vào giá trị của mọi đỉnh thuộc cây con gốc $x$, kể cả $x$;
• $4$ $x$: tính tổng giá trị của mọi đỉnh thuộc cây con gốc $x$, kể cả $x$.

Với thao tác loại $2$ và $4$, chỉ cần in phần dư của tổng khi chia cho $p$. Các phép cộng cũng có thể được lưu theo mô-đun $p$, vì điều này không làm thay đổi bất kỳ kết quả cần in nào. Đặc biệt, nếu $p=1$ thì mọi kết quả đều bằng $0$.

Input

• Dòng đầu chứa bốn số nguyên $n,m,r$ và $p$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

• Mỗi dòng trong $n-1$ dòng tiếp theo chứa hai số nguyên $u$ và $v$, mô tả một cạnh của cây.

• Mỗi dòng trong $m$ dòng cuối mô tả một thao tác theo một trong bốn dạng đã nêu.

Output

• Với mỗi thao tác loại $2$ hoặc $4$, in đáp án theo mô-đun $p$ trên một dòng riêng. Mỗi đáp án nằm trong đoạn từ $0$ đến $p-1$.

Constraints

• $1\le n,m\le 10^5$.
• $1\le r\le n$.
• $1\le p\le 2^{30}$.
• $0\le a_i\le 2.147483647\cdot 10^9$.
• Trong thao tác loại $1$ hoặc $3$: $1\le z\le 2.147483647\cdot 10^9$.
• Mọi chỉ số đỉnh xuất hiện trong thao tác đều thuộc đoạn $1,\dots ,n$.
• $n-1$ cạnh tạo thành một cây vô hướng.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,m\le 40$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

6 10 3 10
2 7 1 4 6 3
3 1
3 4
1 2
4 5
4 6
2 2 5
1 2 6 5
4 4
3 1 4
2 2 5
3 3 3
4 3
1 5 5 7
2 5 5
4 1

0
3
8
4
6
3