Vương quốc Vô Tận được biểu diễn bởi một cây gồm \(N\) thành phố (đánh số từ \(1\) đến \(N\)) và \(N - 1\) con đường hai chiều. Mỗi thành phố \(i\) thuộc về một phe phái tôn giáo \(C_i\) và có mức độ thịnh vượng là \(V_i\). Mỗi con đường thứ \(j\) nối hai thành phố có chiều dài \(W_j\). Khoảng cách giữa hai thành phố \(u\) và \(v\), ký hiệu là \(D(u, v)\), là tổng chiều dài các con đường trên đường đi ngắn nhất giữa chúng.

Nhà vua cần quản lý vương quốc với \(Q\) sự kiện lịch sử xảy ra theo thời gian. Ban đầu (thời điểm \(0\)), vương quốc ở trạng thái sơ khai. Các sự kiện được đánh số từ \(1\) đến \(Q\) theo trình tự thời gian và thuộc một trong \(4\) loại sau:

1. 1 u c v: Lật đổ và thay mới. Thành phố \(u\) bị ép buộc cải đạo sang tôn giáo \(c\) và mức độ thịnh vượng thay đổi thành \(v\).
2. 2 i w: Cải tạo địa hình. Con đường thứ \(i\) (theo thứ tự đầu vào) được xây lại với chiều dài mới là \(w\).
3. 3 u c: Tụ hội tâm linh. Một đại lễ của tôn giáo \(c\) được tổ chức tại thành phố \(u\). Bạn cần tính chi phí tổ chức đại lễ. Chi phí này bằng tổng mức thịnh vượng của các thành phố cùng tôn giáo \(c\) nhân với khoảng cách từ thành phố đó đến \(u\). Cụ thể, gọi \(S(c)\) là tập hợp các thành phố hiện tại đang theo tôn giáo \(c\), bạn cần tính:
   
   \[ \text{Chi phí} = \sum_{x \in S(c)} (D(u, x) \cdot V_x) \pmod{10^9 + 7}. \]
4. 4 k: Vòng lặp thời gian. Một phép thuật lượng tử được thi triển, ngay lập tức đưa toàn bộ vương quốc (tôn giáo, thịnh vượng của các đỉnh và chiều dài của các cạnh) quay ngược về trạng thái chính xác ngay sau khi sự kiện thứ \(k\) kết thúc.

Hãy giúp nhà vua tính toán chi phí cho tất cả các sự kiện tổ chức đại lễ (loại 3).

Input

• Dòng \(1\): Nhập số nguyên \(N, Q\). \((1 \le N, Q \le 10^5)\).
• Dòng \(2\): \(N\) số nguyên \(C_1, C_2, \dots, C_N\) thể hiện tôn giáo ban đầu của các thành phố. \((1 \le C_i \le N)\)
• Dòng \(3\): \(N\) số nguyên \(V_1, V_2, \dots, V_N\) thể hiện mức độ thịnh vượng ban đầu của các thành phố. \((1 \le V_i \le 10^9)\)
• \(N-1\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(u_i, v_i, W_i\) mô tả con đường thứ \(i\) nối giữa hai thành phố \(u_i\) và \(v_i\) với chiều dài ban đầu là \(W_i\). \((1 \le u_i, v_i \le N, 1 \le W_i \le 10^6)\)
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một sự kiện thuộc một trong \(4\) loại trên.
  • Với sự kiện loại 2, chỉ số cạnh luôn thỏa \(1 \le i \le N-1\).
  • Với sự kiện loại 4, luôn có \(0 \le k < t\), trong đó \(t\) là số thứ tự của truy vấn hiện tại. Giá trị \(0\) biểu thị trạng thái trước khi có bất kỳ truy vấn nào.

Output

• Với mỗi sự kiện loại 3, in ra chi phí tổ chức (kết quả chia lấy dư \(10^9 + 7\)) trên một dòng riêng biệt.

Example

3 4
1 2 1
10 20 30
1 2 5
2 3 5
3 2 1
1 2 1 10
2 1 10
3 2 1

200
250

3 6
1 2 1
10 20 30
1 2 5
2 3 5
3 2 1
1 2 1 10
2 1 10
3 2 1
4 1
3 2 1

200
250
200

Scoring

• Subtask \(1\) (\(20\%\) điểm): \(1 \le N, Q \le 10\).
• Subtask \(2\) (\(30\%\) điểm): \(1 \le N, Q \le 100\), không có sự kiện loại 2 và sự kiện loại 4.
• Subtask \(3\) (\(50\%\) điểm): Không có ràng buộc gì thêm.