Có \(N\) bóng đèn được nối với nhau thành một cây gồm \(N\) đỉnh, gốc cây là đỉnh \(1\). Mỗi bóng đèn \(i\) có điện trở \(R_i\). Ban đầu, tất cả các bóng đèn đều đang bật và hệ thống ở phiên bản \(0\). Mỗi phiên bản lưu lại trạng thái độc lập của toàn bộ hệ thống. Các phiên bản được đánh số từ \(0\) theo thứ tự được tạo ra. Với một phiên bản bất kỳ, gọi

là tổng điện trở của tất cả các bóng đang bật. Nguồn điện có hiệu điện thế không đổi \(U\). Khi đó dòng điện chạy trong mạch là

Công suất của bóng đèn \(i\) nếu bóng đang bật là

Bóng đang tắt có công suất bằng \(0\) và không đóng góp vào \(S\). Điện trở của bóng đèn vẫn được giữ nguyên khi bóng bị tắt. Nếu bóng được bật lại, nó sử dụng điện trở hiện tại của mình.

Các thao tác

Có \(Q\) truy vấn thuộc một trong ba loại.

Loại 1: 1 k v x

Tạo một phiên bản mới từ phiên bản \(k\). Chỉ thay đổi điện trở của bóng \(v\):

Các bóng khác và trạng thái bật/tắt được giữ nguyên. Đảm bảo sau khi cập nhật \(R_v\ge1\).

Loại 2: 2 k v

Tạo một phiên bản mới từ phiên bản \(k\) và đảo trạng thái của bóng \(v\): nếu \(v\) đang bật thì tắt, nếu \(v\) đang tắt thì bật. Điện trở của bóng \(v\) không thay đổi. Đảm bảo sau thao tác vẫn có ít nhất một bóng đang bật.

Loại 3: 3 k u v

Xét hệ thống ở phiên bản \(k\). Gọi \(P\) là tổng công suất của tất cả các bóng đang bật nằm trên đường đi đơn từ \(u\) đến \(v\). Nếu

thì

Hãy in \(P\) dưới dạng phân số tối giản \(\frac{a}{b}\), trong đó \(a,b\) là hai số nguyên, \(a\ge0\), \(b>0\) và \(\gcd(a,b)=1\). Nếu \(P=0\), phải in 0 1. Truy vấn loại \(3\) không tạo phiên bản mới.

Input

• Dòng đầu tiên chứa ba số nguyên \(N,U,Q\).
• Dòng thứ hai chứa \(N\) số nguyên \(R_1,R_2,\ldots,R_N\).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\), biểu diễn một cạnh của cây.
• \(Q\) dòng tiếp theo chứa một truy vấn.

Phiên bản ban đầu có số hiệu \(0\). Mỗi truy vấn loại \(1\) hoặc loại \(2\) tạo ra đúng một phiên bản mới. Nếu đây là phiên bản mới thứ \(j\) được tạo ra thì nó có số hiệu \(j\). Với mọi truy vấn, phiên bản \(k\) phải là một phiên bản đã tồn tại.

Constraints

• \(1\le N,Q\le10^5\)
• \(1\le U\le10^9\)
• \(1\le R_i\le10^9\)
• \(|x|\le10^9\)
• \(1\le u,v\le N\)

Đảm bảo sau mỗi thao tác loại \(1\): \(R_v\ge1\). Đảm bảo trong mọi phiên bản có ít nhất một bóng đang bật.

Output

Với mỗi truy vấn loại \(3\), in ra một dòng gồm hai số nguyên \(a,b\), biểu diễn giá trị \(P=\frac{a}{b}\) dưới dạng phân số tối giản. Nếu \(P=0\), in 0 1.

Example

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

3 2
200 121
25 32
16 9

Scoring

• Subtask 1 (20 points): \(N,Q\le1000\); chỉ có truy vấn loại \(3\) (phiên bản \(k\) luôn bằng \(0\)).
• Subtask 2 (80 points): \(N,Q\le10^5\); không có điều kiện gì thêm.