Faker -- huyền thoại sống của Liên Minh Huyền Thoại luôn tỏa ra một khí chất lạnh lùng nhưng đầy uy lực. Trên sân khấu, ánh mắt anh sắc bén như thể nhìn thấu mọi bước đi của đối thủ. Những cú di chuyển chuẩn xác, những pha xử lý điêu luyện và tự tin biến Faker thành trung tâm của mọi ánh nhìn. Anh không cần khoa trương, chỉ bằng sự bình tĩnh và phong thái như một "quái vật thầm lặng", Faker khiến người xem vừa nể phục vừa bị cuốn hút. Trong khoảnh khắc quan trọng, khi cả thế giới dõi theo, anh như hóa thân thành "Quỷ Vương Bất Diệt", ung dung định đoạt trận đấu bằng vài thao tác gọn gàng, để rồi khán giả chỉ có thể thốt lên: "Đúng là Faker -- huyền thoại không có người thứ hai".

Mùa chung kết thế giới năm nay, Faker cùng T1 đứng trước cơ hội để viết tiếp một chương nữa cho cuốn tiểu thuyết Chúng tôi đã thống trị thế giới bằng cách nào, bằng việc dành chiếc Summoner's Cup thứ sáu cho SKT-T1, và là chức vô địch thứ ba liên tiếp. Chính vì lẽ đó, hai con số \(3\) và \(6\) được xem là thần số học của Faker năm nay. Trong bài toán này, ta hãy cùng khám phá một loại con số đặc biệt, được gọi là Faker number.

Một số nguyên không âm \(x\) được gọi là Faker Number khi và chỉ khi nó thỏa mãn hai điều kiện sau:

• Trong biểu diễn thập phân, \(x\) chỉ chứa các chữ số \(3\) và \(6\); và số chữ số \(3\) bằng số chữ số \(6\).
• Tỷ lệ đối xứng của \(x\) lớn hơn \(50 \%\).

Tỷ lệ đối xứng của số nguyên không âm \(x\) được xác định như sau. Giả sử biểu diễn thập phân của \(x\) có dạng \(\chi_1 \chi_2 \ldots \chi_{\eta}\), vơi \(\eta\) là số chữ số của \(x\), \(\chi_1\) là chữ số lớn nhất \((\chi_1 > 0)\) và \(\chi_{\eta}\) là chữ số hàng đơn vị. Khi đó:

• Gọi \(\alpha(x)\) là số cặp chỉ số \((\mu, \nu)\) sao cho \(1 \leq \mu \leq \nu \leq \eta\) và dãy chữ số \(\chi_{\mu} \chi_{\mu + 1} \chi_{\mu + 2} \ldots \chi_{\nu}\) là một dãy đối xứng. Một dãy đối xứng là dãy mà đọc từ trái qua phải hay từ phải qua trái đều như sau.
• Gọi \(\beta(x)\) là số cặp chỉ số \((\mu, \nu)\) sao cho \(1 \leq \mu \leq \nu \leq \eta\).
• Tỉ lệ đối xứng của \(x\) được tính theo công thức \(\gamma(x) = \frac{\alpha(x)}{\beta(x)}\).

Ví dụ:

• Với \(x = 3366\), ta có \(\alpha(x) = 6\), \(\beta(x) = 10\). Tỷ lệ đối xứng là \(\gamma(x) = \frac{6}{10}\).
• Với \(x = 336366\), ta có \(\alpha(x) = 10\), \(\beta(x) = 21\). Tỷ lệ đối xứng là \(\gamma(x) = \frac{10}{21}\).
  Từ định nghĩa trên, ta có thể thấy \(36\) hay \(3366\) là các Faker number, còn \(363\) hay \(336366\) thì không.

Bạn được cho một cây gồm \(n\) đỉnh. Các đỉnh được đánh số từ \(1\) đến \(n\). Gốc của cây là đỉnh \(1\). Mỗi đỉnh có giá trị là một số nguyên không âm. Ban đầu, giá trị của các đỉnh lần lượt là \(a_1, a_2, \ldots, a_n\). Bạn cần thực hiện \(q\) thao tác, mỗi thao tác thuộc một trong ba dạng sau:

• \(1\) \(u\) \(v\) \(x\): Tăng giá trị các đỉnh trên đường đi từ \(u\) đến \(v\) (bao gồm cả \(u\) và \(v\)) thêm \(x\).
• \(2\) \(u\) \(v\): Đếm số đỉnh trên đường đi từ \(u\) đến \(v\) (bao gồm cả \(u\) và \(v\)) có giá trị là một Faker Number.
• \(3\) \(u\): Đếm số đỉnh thuộc cây con gốc \(u\) có giá trị là một Faker Number.

Dữ liệu

Vào từ file văn bản fakernum.inp:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \le n \le 10^5, 1 \le q \le 5 \cdot 10^5 )\) lần lượt là số đỉnh của cây và số thao tác cần thực hiện.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((0 \leq a_i \leq 10^{16})\) thể hiện giá trị ban đầu của các đỉnh trên cây.
• Trong \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \le u, v \le n)\) cho biết trên cây có một cạnh nối hai đỉnh \(u\) và \(v\).
• Trong \(q\) dòng cuối cùng, mỗi dòng mô tả một thao tác theo một trong ba dạng ở trên. Các tham số của các thao tác thỏa mãn \(1 \le u, v \le n\) và \(1 \le x \le 10^{16}\). Dữ liệu đảm bảo trong mọi thời điểm, giá trị của mọi đỉnh trên cây không vượt quá \(10^{16}\).

Kết quả

Ghi ra file văn bản fakernum.out:

• Với mỗi thao tác loại \(2\) và \(3\), in ra trên một dòng một số nguyên duy nhất là kết quả của thao tác đó.

Ràng buộc

• Subtask \(1\) (\(13\) điểm): \(n \le 1000, q \le 5000\).
• Subtask \(2\) (\(17\) điểm): Không có thao tác loại \(1\).
• Subtask \(3\) (\(19\) điểm): \(a_1 = a_2 = \ldots = a_n = 0\) và trong mọi thao tác loại \(1\), \(x = 1\).
• Subtask \(4\) (\(19\) điểm): Cây thỏa mãn tính chất sau: tồn tại một hoán vị \((p_1, p_2, \ldots, p_n)\) của các số \((1, 2, \ldots, n)\) sao cho với mọi \(2 \leq i \leq n\), có một cạnh nối hai đỉnh \(p_i\) và \(p_{\lfloor \frac{i}{2} \rfloor}\).
• Subtask \(5\) (\(19\) điểm): Cây thỏa mãn tính chất sau: tồn tại một hoán vị \((p_1, p_2, \ldots, p_n)\) của các số \((1, 2, \ldots, n)\) sao cho với mọi \(2 \leq i \leq n\), có một cạnh nối hai đỉnh \(p_i\) và \(p_{i - 1}\).
• Subtask \(6\) (\(13\) điểm): Không có ràng buộc gì thêm.

Ví dụ

5 7
0 0 0 0 0
1 2
1 3
3 5
3 4
1 2 4 3
1 5 5 3
1 2 5 33
1 4 4 33
2 1 4
2 2 3
3 3

3
3
3