Đế chế Vô Cực được mô tả bởi 25 đại lượng số và 7 khối dữ liệu. Hội đồng Tối cao yêu cầu bạn tính 24 chỉ số \(A_1,\dots,A_{24}\) và một mã niêm phong \(FINAL\). Sai một chỉ số thì \(FINAL\) cũng sai.

Các đối tượng trong đề:

• Cây \(T\): \(n\) đỉnh, gốc là đỉnh \(1\), cha của đỉnh \(i\) là \(par_i\) với \(par_i < i\). Đỉnh \(i\) có trọng số \(w_i\), màu \(c_i\) và một xâu \(s_i\) gồm chữ cái thường. Quy ước \(dep(1)=0\), \(dep(v)=dep(par_v)+1\); \(sub(v)\) là cây con gốc \(v\), \(sz(v)=|sub(v)|\).
• Đồ thị có hướng \(G\): \(n\) đỉnh, \(m\) cung, cho phép cung lặp.
• Mạng luồng \(F\): \(Nf\) đỉnh, \(Mf\) cung có hướng kèm sức chứa.
• Đồ thị vô hướng động \(H\): \(n\) đỉnh, ban đầu không cạnh, biến đổi qua \(T\) thao tác.
• Mảng \(a_1..a_A\), ma trận chi phí \(Cost_{Gm\times Gm}\), ma trận \(M_{Ms\times Ms}\).

Bộ sinh ngẫu nhiên chuẩn

Một số chỉ số dùng dãy giả ngẫu nhiên xorshift64 sau (số nguyên 64 bit không dấu):

unsigned long long rngState;
void seedRng(unsigned long long X0, unsigned long long phase) {
    unsigned long long x = X0 ^ (phase * 0x9E3779B97F4A7C15ULL);
    if (x == 0) x = 88172645463325252ULL;
    rngState = x;
}
unsigned long long nxt() {
    rngState ^= rngState << 13;
    rngState ^= rngState >> 7;
    rngState ^= rngState << 17;
    return rngState;
}

Trước mỗi chỉ số có dùng bộ sinh phải gọi lại seedRng(X0, <số hiệu chỉ số>). Trong một chỉ số, các lời gọi nxt() phải theo đúng thứ tự mô tả, kể cả khi giá trị sinh ra không dùng đến.

Ký hiệu \(md(x) = ((x \bmod MOD) + MOD) \bmod MOD\) và phép gộp băm \(fold(h,v) = (h \cdot 1000003 + md(v)) \bmod MOD\).

24 chỉ số cần tính

\(A_1\) — Thao tác đường đi trên cây. Mỗi đỉnh khởi tạo \(val_i = w_i\). Gọi seedRng(X0, 1), \(H=0\). Lặp \(q\) lần, mỗi lần lấy đúng thứ tự \(u = nxt()\%n+1\), \(v = nxt()\%n+1\), \(t = nxt()\%4\), \(x = nxt()\%W+1\), rồi:

• \(t=0\): cộng \(x\) vào mọi đỉnh trên đường đi \(u \to v\);
• \(t=1\): gán \(x\) cho mọi đỉnh trên đường đi \(u \to v\);
• \(t=2\): \(H \leftarrow fold(H,\ \text{tổng } val \text{ trên đường đi } u \to v)\);
• \(t=3\): \(H \leftarrow fold(H,\ (\max val \text{ trên đường đi } u \to v) + dep(lca(u,v)))\).

\(A_1 = H\).

\(A_2\) — Phần tử nhỏ thứ \(k\) trong cây con. Với mỗi \(z = sp_1, sp_2, \dots, sp_S\) theo đúng thứ tự trong input, đặt \(k = ((K+z) \bmod sz(z)) + 1\) và lấy \(v_z\) là giá trị \(w\) nhỏ thứ \(k\) trong đa tập \(\{w_u : u \in sub(z)\}\). \(A_2\) là kết quả \(fold\) lần lượt các \(v_z\), bắt đầu từ \(0\).

\(A_3\) — Đếm cặp gần nhau. Số cặp không thứ tự \((u,v)\), \(u<v\), có khoảng cách (số cạnh) trên cây \(T\) không vượt quá \(D\). Giá trị nguyên chính xác, không lấy mod.

\(A_4\) — Số màu phân biệt trong cây con. Gọi \(d(i)\) là số màu phân biệt trong \(\{c_u : u \in sub(i)\}\). \(A_4 = \left(\sum_{i=1}^{n} i \cdot d(i)\right) \bmod MOD\).

\(A_5\) — Số xâu con phân biệt. Số xâu khác rỗng xuất hiện như xâu con của ít nhất một \(s_i\). Nguyên chính xác.

\(A_6\) — Tổng số lần xuất hiện. \(A_6 = \sum_{i=1}^{n}\sum_{j=1}^{n} (\text{số vị trí } p \text{ mà } s_j \text{ xuất hiện tại } p \text{ trong } s_i)\). Tính cả \(j=i\), và đếm mọi vị trí chứ không phải mỗi \(j\) một lần.

\(A_7\) — Tổng mảng LCP. Đặt \(TCAT = s_1 + \texttt{\#} + s_2 + \texttt{\#} + \dots + \texttt{\#} + s_n\) (ký tự ngăn cách #, mã ASCII 35), độ dài \(L\). Gọi \(sa_0..sa_{L-1}\) là mảng hậu tố theo thứ tự từ điển tăng dần, \(lcp_i = LCP(sa_{i-1}, sa_i)\) với \(i \ge 1\). \(A_7 = \sum_{i=1}^{L-1} lcp_i\). Nguyên chính xác.

\(A_8\) — Truy vấn LCP ngẫu nhiên. Gọi seedRng(X0, 8). Lặp đúng 1000 lần: \(i = nxt()\%L\), \(j = nxt()\%L\); cộng vào tổng giá trị \(LCP(TCAT[i..],\ TCAT[j..])\) — nếu \(i=j\) thì giá trị đó bằng \(L-i\). \(A_8\) là tổng thu được. Nguyên chính xác.

\(A_9\) — Hàm Z. Gọi \(z_0..z_{L-1}\) là hàm Z của \(TCAT\) với quy ước \(z_0 = L\). \(A_9 = \sum_{i=0}^{L-1} z_i\). Nguyên chính xác.

\(A_{10}\) — Số thành phần liên thông mạnh của đồ thị có hướng \(G\).

\(A_{11}\) — Đường đi nặng nhất trên đồ thị rút gọn. Rút gọn \(G\) thành DAG, mỗi đỉnh rút gọn mang trọng số bằng số đỉnh của thành phần đó. \(A_{11}\) là trọng số lớn nhất của một đường đi có hướng trên DAG; đường đi gồm đúng một đỉnh cũng hợp lệ.

\(A_{12}\) — 2-SAT. Có các biến logic \(x_1,\dots,x_C\). Với mỗi cung \((u,v)\) của \(G\):

• nếu \(u+v\) chẵn, thêm mệnh đề \((x_{c_u} \lor x_{c_v})\);
• nếu \(u+v\) lẻ, thêm mệnh đề \((\lnot x_{c_u} \lor \lnot x_{c_v})\).

\(A_{12} = 1\) nếu hệ thoả mãn được, ngược lại \(A_{12} = 0\).

\(A_{13}\) — Luồng cực đại từ đỉnh \(1\) đến đỉnh \(Nf\) trên mạng \(F\).

\(A_{14}\) — Ghép cặp chi phí nhỏ nhất. \(A_{14} = \min_{p} \sum_{i=0}^{Gm-1} Cost[i][p(i)]\) với \(p\) chạy trên mọi hoán vị của \(\{0,\dots,Gm-1\}\).

\(A_{15}\) — Quy hoạch động lồi. Đặt \(P_0 = 0\), \(P_i = a_1 + \dots + a_i\). Với \(dp_0 = 0\) và \(i \ge 1\):

\(A_{15} = dp_A\). Nguyên chính xác, vừa kiểu 64 bit có dấu.

\(A_{16}\) — Đếm giá trị phân biệt trên đoạn. Gọi seedRng(X0, 16). Lặp \(Qm\) lần: \(l = nxt()\%A+1\), \(r = nxt()\%A+1\), nếu \(l>r\) thì đổi chỗ. \(A_{16}\) là tổng, trên mọi truy vấn, của số giá trị phân biệt trong \(a_l..a_r\).

\(A_{17}\) — Liên thông động. Số thao tác loại \(3\) cho câu trả lời "cùng thành phần liên thông".

\(A_{18}\) — Chặn trên đoạn. Mảng \(b_1..b_A\) khởi tạo \(b_i = a_i\). Gọi seedRng(X0, 18), \(H=0\). Lặp \(q\) lần, lấy đúng thứ tự \(t = nxt()\%4\), \(r_1 = nxt()\), \(r_2 = nxt()\), \(r_3 = nxt()\); đặt \(l = r_1 \bmod A\), \(r = r_2 \bmod A\) (chỉ số 0-based), nếu \(l>r\) đổi chỗ; đoạn thao tác là \(b_{l+1..r+1}\):

• \(t=0\): \(b_i \leftarrow \min(b_i,\ r_3 \bmod 2000000 + 1)\) với mọi \(i\) trong đoạn;
• \(t=1\): \(b_i \leftarrow b_i + (r_3 \bmod Wa + 1)\);
• \(t=2\): \(H \leftarrow fold(H, \text{tổng } b \text{ trên đoạn})\);
• \(t=3\): \(H \leftarrow fold(H, \max b \text{ trên đoạn})\).

\(A_{18} = H\).

\(A_{19}\) — Dãy động. Dãy \(v\) khởi tạo là \(a_1..a_A\). Gọi seedRng(X0, 19), \(H=0\). Lặp \(q\) lần, lấy đúng thứ tự \(t = nxt()\%5\), \(r_1 = nxt()\), \(r_2 = nxt()\). Gọi \(sz\) là độ dài hiện tại của \(v\):

• \(t=0\): \(p = r_1 \bmod (sz+1) + 1\), \(x = r_2 \bmod Wa + 1\); chèn \(x\) vào vị trí \(p\);
• nếu \(t \ne 0\) và \(sz = 0\): bỏ qua thao tác này;
• \(t=1\): \(p = r_1 \bmod sz + 1\); xoá phần tử thứ \(p\);
• \(t=2\): \(l = r_1 \bmod sz + 1\), \(r = r_2 \bmod sz + 1\), nếu \(l>r\) đổi chỗ; đảo ngược \(v_l..v_r\);
• \(t=3\): \(l, r\) như trên; \(H \leftarrow fold(H, v_l + \dots + v_r)\);
• \(t=4\): \(p = r_1 \bmod sz + 1\); \(H \leftarrow fold(H, v_p)\).

\(A_{19} = H\).

\(A_{20}\) — Phân tích thừa số. Gọi \(\varphi\) là hàm Euler và \(P^+(Nb)\) là ước nguyên tố lớn nhất của \(Nb\). \(A_{20} = \left(md(\varphi(Nb)) \cdot 1000003 + md(P^+(Nb))\right) \bmod MOD\).

\(A_{21}\) — Thặng dư Trung Hoa. Số nguyên không âm nhỏ nhất \(x\) thoả \(x \equiv r_1 \pmod{m_1}\) và \(x \equiv r_2 \pmod{m_2}\); nếu không tồn tại thì \(A_{21} = -1\). Nguyên chính xác, không lấy mod.

\(A_{22}\) — Tổng Möbius. \(A_{22} = \left(\sum_{i=1}^{Lm} \mu(i) \cdot \lfloor Lm/i \rfloor^2\right) \bmod MOD\), kết quả nằm trong \([0, MOD)\).

\(A_{23}\) — Tích chập với mô-đun bất kỳ. Đặt \(nf = \min(n, 32768)\), \(ng = \min(A, 32768)\), \(F_i = w_{i+1} \bmod MOD\) với \(0 \le i < nf\), và \(G_i = a_{i+1} \bmod MOD\) với \(0 \le i < ng\). Gọi \(h = F * G\) là tích chập, độ dài \(nf+ng-1\), các hệ số lấy theo \(MOD\). \(A_{23} = \left(\sum_{i=0}^{nf+ng-2} (i+1) \cdot h_i\right) \bmod MOD\).

\(A_{24}\) — Lũy thừa ma trận. \(A_{24} = \operatorname{tr}(M^E) \bmod MOD\), lũy thừa trên vành \(\mathbb{Z}_{MOD}\).

\(FINAL\). Đặt \(H = 0\), rồi với \(i = 1,2,\dots,24\) thực hiện \(H \leftarrow fold(H, A_i)\). Kết quả \(FINAL = H\).

Input

• Dòng 1: \(n\) \(m\) \(q\) \(S\) \(C\)
• Dòng 2: \(A\) \(Qm\) \(T\) \(Nf\) \(Mf\)
• Dòng 3: \(Gm\) \(Ms\) \(Lm\) \(K\) \(D\)
• Dòng 4: \(MOD\) \(E\) \(X0\) \(W\) \(Wa\)
• Dòng 5: \(Nb\) \(r_1\) \(m_1\) \(r_2\) \(m_2\)
• Dòng 6: \(n\) số nguyên \(w_1 \dots w_n\)
• Dòng 7: \(n\) số nguyên \(c_1 \dots c_n\)
• \(n\) dòng tiếp theo: xâu \(s_1, s_2, \dots, s_n\), mỗi xâu một dòng
• Dòng tiếp theo: \(n-1\) số nguyên \(par_2\ par_3 \dots par_n\)
• Dòng tiếp theo: \(S\) số nguyên \(sp_1 \dots sp_S\) (danh sách đỉnh đặc biệt)
• \(m\) dòng tiếp theo: mỗi dòng hai số \(u\) \(v\) — một cung có hướng của \(G\)
• \(Mf\) dòng tiếp theo: mỗi dòng ba số \(u\) \(v\) \(cap\) — một cung có hướng của mạng \(F\)
• \(Gm\) dòng tiếp theo: mỗi dòng \(Gm\) số — ma trận \(Cost\)
• \(Ms\) dòng tiếp theo: mỗi dòng \(Ms\) số — ma trận \(M\)
• Dòng tiếp theo: \(A\) số nguyên \(a_1 \dots a_A\)

• \(T\) dòng tiếp theo: mỗi dòng ba số \(t\) \(u\) \(v\) — thao tác trên đồ thị vô hướng \(H\):

  • 1 u v — thêm cạnh \((u,v)\); đảm bảo cạnh này chưa tồn tại;
  • 2 u v — xoá cạnh \((u,v)\); đảm bảo cạnh này đang tồn tại;
  • 3 u v — hỏi \(u\) và \(v\) có cùng thành phần liên thông không.

  Cạnh là vô hướng: \((u,v)\) và \((v,u)\) là một cạnh.

Ràng buộc

• \(2 \le n \le 10^5\); \(1 \le m \le 2\cdot10^5\); \(1 \le q \le 10^5\)
• \(1 \le S \le \min(n, 3000)\); \(2 \le C \le 10^5\)
• \(1 \le A \le 10^5\); \(1 \le Qm \le 10^5\); \(1 \le T \le 10^5\)
• \(2 \le Nf \le 5000\); \(1 \le Mf \le 3\cdot10^4\)
• \(1 \le Gm \le 100\); \(1 \le Ms \le 60\); \(1 \le Lm \le 2\cdot10^6\)
• \(1 \le K \le 10^9\); \(0 \le D \le n\)
• \(2 \le MOD \le 10^9\) — không nhất thiết là số nguyên tố
• \(1 \le E \le 10^{18}\); \(1 \le X0 \le 2^{63}-1\)
• \(1 \le W \le 10^6\); \(1 \le Wa \le 1000\)
• \(2 \le Nb \le 10^{18}\); \(1 \le m_1, m_2 \le 10^9\); \(0 \le r_1 < m_1\); \(0 \le r_2 < m_2\)
• \(1 \le w_i \le W\); \(1 \le c_i \le C\); \(1 \le a_i \le Wa\)
• \(s_i\) gồm chữ cái thường a–z, \(1 \le |s_i| \le 6\)
• \(1 \le par_i < i\) (nên đỉnh \(1\) là gốc); \(1 \le sp_i \le n\)
• Cung của \(G\): \(1 \le u, v \le n\), \(u \ne v\)
• Cung của \(F\): \(1 \le u, v \le Nf\), \(u \ne v\), \(1 \le cap \le 10^6\)
• \(1 \le Cost[i][j] \le 10^6\); \(0 \le M[i][j] < MOD\)

Output

• In ra đúng 25 dòng: lần lượt \(A_1\), \(A_2\), \(\dots\), \(A_{24}\), rồi \(FINAL\), mỗi giá trị trên một dòng.

Example

7 10 2 5 40
1 2 3 5 7
2 2 16 236809254 1
707371352 1 4371512876906363005 6 2
9973 7 9 4 7
4 2 6 3 3 1 3
4 29 9 9 6 8 30
dcc
d
e
bb
b
ae
f
1 1 2 3 4 5
6 6 1 3 6
5 6
3 4
3 1
5 3
6 1
1 3
1 2
5 7
6 2
6 2
4 5 1
3 4 2
3 4 4
2 4 3
3 5 9
1 3 1
3 4 3
176138 116289
563811 237751
331690207 188107718
534250052 699825301
2
3 2 2
3 2 1
1 1 2

6
24146249
6
52
11
11
13
698
18
6
5
0
1
413889
236809258
2
1
4
4
68840961
25
159
160
324144156
216563007