Mathematical Algorithms TWK Open ∮

Vào một buổi sáng, khi Youtuber_TWK đang nhâm nhi trà đá cùng kyanh thì bỗng Youtuber_TWK nhận được tin nhắn từ crush rằng:

"Chị cảm ơn vì em đã tỏ tình chị nhưng điều kiện của chị hơi khó. Do bố chị là giáo viên Toán nên em phải giải một bài toán mới có thể làm rể nhà chị."

Đọc xong tin nhắn, Youtuber_TWK liền trầm ngâm suy nghĩ. Lúc này, kyanh nhòm lại thì thấy nội dung bài toán:

Crush của Youtuber_TWK cho một dãy số:

2, 8, 20, 40, 70, 112, ...

Dãy số trên được sinh ra theo một quy luật nhất định.

Gợi ý: Hãy thử xét hiệu giữa hai số liên tiếp. Nếu vẫn chưa nhận ra quy luật, hãy tiếp tục xét hiệu của các hiệu vừa tìm được.

Với tình anh em chí cốt, kyanh quyết định NHỜ bạn giải hộ bài này.

Yêu cầu: bạn hãy tìm số thứ \(N\) của dãy trên.

Input

• 1 số \(N\) được nhập từ bàn phím \((1≤N≤10^5)\)

Output

• In ra màn hình kết quả.

Example

5

70

100

343400

Chỉ còn đúng một ngày nữa là đến lễ tốt nghiệp. Ba người bạn thân là Youtuber_TWK, TheLegendOfSpirit và Nhan456 đang cùng nhau dọn dẹp lại phòng tin trước khi ra trường.

Trong lúc lục lại đống tài liệu cũ, cả ba phát hiện một cuốn sổ bí ẩn do các anh chị khóa trước để lại. Bên trong ghi một dãy số nguyên: \(a₁, a₂, ..., aₙ\)

Kèm theo đó là lời nhắn:

"Ai giải được bí mật của cuốn sổ này sẽ nhận được món quà tốt nghiệp đặc biệt."

Tò mò, cả ba bắt đầu nghiên cứu. Họ nhận ra cuốn sổ liên tục thay đổi dữ liệu và đưa ra các yêu cầu kiểm tra. Mỗi yêu cầu thuộc một trong hai loại:

• Loại 1: 1 i x

Một thông tin trong cuốn sổ bị cập nhật. Giá trị tại vị trí \(i\) được thay bằng \(x\).

• Loại 2: 2 l r

Cuốn sổ yêu cầu tìm mức tăng lớn nhất giữa hai vị trí trong đoạn từ \(l\) đến \(r\).

Cụ thể, cần tìm giá trị lớn nhất của: \(a[j] - a[i]\) với \(l ≤ i < j ≤ r\)

Nếu \(r−l+1<2\), in \(-1\).
Kết quả có thể âm nếu tất cả các cặp \(i<j\) trong đoạn đều cho giá trị \(a[j]−a[i]≤0\).

Vì thời gian đến lễ tốt nghiệp không còn nhiều, Youtuber_TWK, TheLegendOfSpirit và Nhan456 quyết định nhờ bạn giải giúp toàn bộ các truy vấn để khám phá bí mật cuối cùng của cuốn sổ.

Input

• Dòng đầu gồm hai số nguyên \(N,Q\). \((1≤N,Q≤5×10^5)\)
• Dòng thứ hai gồm \(N\) số nguyên \(a_i\). \((−10^9≤a_i​,x≤10^9)\)
• \(Q\) dòng tiếp theo mô tả các truy vấn.

Output

• Với mỗi truy vấn loại 2, in ra đáp án trên một dòng.

Example

5 4
1 5 2 8 4
2 1 5
1 3 10
2 1 5
2 2 4

7
9
5

6 6
9 7 5 3 1 0
2 1 6
1 6 100
2 1 6
2 4 6
2 5 5
2 2 3

-1
99
99
-1
-2

Youtuber_TWK và kyanh đang tham gia tiết học chế tạo robot.

Có \(n\) robot. Robot thứ \(i\) có tập các trạng thái hoạt động được biểu diễn bởi \(m_i\) điểm:

\((x_{i,1},y_{i,1}), (x_{i,2},y_{i,2}), \dots, (x_{i,m_i},y_{i,m_i})\)

Trong đó:

• \(x_{i,j}\) là số linh kiện mà robot có thể lắp ráp trong một giờ. (\(|x_{i,j}| \le 10^9\))
• \(y_{i,j}\) là lượng điện năng tiêu thụ tương ứng. (\(|y_{i,j}| \le 10^9\))

Sau khi được Youtuber_TWK nâng cấp bộ điều khiển và kyanh hiệu chỉnh thuật toán cân bằng năng lượng, robot có thể hoạt động ở bất kỳ trạng thái nào nằm trong bao lồi của các điểm trên.

Giả sử robot \(i\) chọn trạng thái \((X_i,Y_i)\).

Để hoàn thành bài thực hành, kyanh yêu cầu tổng số linh kiện được lắp ráp bởi tất cả robot phải đúng bằng

Hãy giúp Youtuber_TWK tìm cách vận hành các robot sao cho tổng điện năng tiêu thụ là nhỏ nhất, tức là tối thiểu hóa

Input

Dòng đầu gồm hai số \(n,S\) (\(1\le n\le 2\cdot 10^5\), \(|S|\le 10^{14}\)).

Tiếp theo với mỗi robot:

• Một dòng chứa \(m_i\).
• \(m_i\) dòng tiếp theo, mỗi dòng chứa hai số \(x_j,y_j\).

Ràng buộc:

Output

In ra giá trị nhỏ nhất của

Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá \(10^{-9}\).

Example

2 5
3
0 0
2 2
4 8
3
0 1
3 2
5 10

4.000000000

3 17
4
0 0
5 4
10 15
15 30
4
0 1
5 6
10 14
15 25
4
0 2
5 5
10 16
15 28

18.200000000

Youtuber_TWK và kyanh đang tham gia một tiết học về lý thuyết tập hợp.

Có một tập hợp gồm \(n\) phần tử được đánh số từ \(0\) đến \(n-1\) và một mảng \(A\) gồm \(2^n\) phần tử.

Mỗi số nguyên \(x\) từ \(0\) đến \(2^n-1\) biểu diễn một tập con \(S\) của tập \({0,1,\ldots,n-1}\) bằng biểu diễn bitmask:

• bit thứ \(i\) của \(x\) bằng \(1\) khi và chỉ khi \(i \in S\);
• \(A[x]\) là giá trị được gán cho tập con \(S\).

Với hai hàm \(F\) và \(G\) trên các tập con, định nghĩa subset convolution: \((F * G)[S] = \sum_{X \subseteq S} F[X] \cdot G[S \setminus X]\).

Cho ba tập con có thứ tự \((S_1,S_2,S_3)\) của \(S\). Bộ ba này được gọi là một phân chia hợp lệ nếu:

\(S_1 \cap S_2 = S_1 \cap S_3 = S_2 \cap S_3 = \varnothing\) và \(S_1 \cup S_2 \cup S_3 = S\).

Các tập \(S_1,S_2,S_3\) có thể rỗng và thứ tự của chúng được phân biệt.

Trọng số của một phân chia hợp lệ là: \(A[S_1] \cdot A[S_2] \cdot A[S_3]\). Với mỗi tập con \(S\), hãy tính tổng trọng số của tất cả các phân chia hợp lệ của \(S\).

Nói cách khác, cần tính: \(B[S] = \sum A[S_1] \cdot A[S_2] \cdot A[S_3]\) trên mọi bộ ba \((S_1,S_2,S_3)\) thỏa mãn các điều kiện trên.

Tất cả kết quả phải được lấy modulo \(998244353\).

Input

• Dòng đầu tiên chứa một số nguyên \(n\).

• Dòng thứ hai chứa \(2^n\) số nguyên \(A[0], A[1], \ldots, A[2^n-1]\).

• Các giá trị thỏa mãn \(0 \le A[i] < 998244353\).

Output

• In ra \(2^n\) số nguyên \(B[0],B[1],\ldots,B[2^n-1]\).

• Giá trị \(B[x]\) phải là đáp án tương ứng với tập con được biểu diễn bởi bitmask \(x\), lấy modulo \(998244353\).

Constraints

• \(1 \le n \le 20\).
• \(0 \le A[i] < 998244353\).

Example

2
1 2 3 4

1 6 9 48

3
1 2 3 4 5 6 7 8

1 6 9 48 15 78 111 516

Youtuber_TWK vừa đăng một video giới thiệu bài guitar mới tại: Click here to listen

Sau khi xem video, Youtuber_TWK ghi lại toàn bộ chuỗi ký tự mô tả quá trình luyện tập thành một xâu \(S\) có độ dài \(n\).

Tuy nhiên, trong quá trình biên tập, có một số đoạn ký hiệu bị lỗi hoặc không mong muốn. Những đoạn này được cho bởi \(m\) xâu cấm:

\(P_1, P_2, ..., P_m.\)

Youtuber_TWK gọi một đoạn nhật ký \(S[l..r]\) là đẹp nếu đồng thời thỏa mãn:

• \(S[l..r]\) là một palindrome.
• \(S[l..r]\) không chứa bất kỳ xâu cấm nào trong số \(P_1, P_2, ..., P_m\) làm xâu con.

Hãy giúp Youtuber_TWK đếm xem có bao nhiêu xâu con đẹp trong xâu \(S\).

Input

• Dòng đầu chứa xâu \(S\). \((1 ≤ |S| ≤ 10^6)\)
• Dòng tiếp theo chứa số nguyên \(m\). \((1 ≤ m ≤ 7 \cdot 10^6)\)
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa xâu cấm \(P_i\). \((1 ≤ |Pi|\) \(,\) \(∑|Pi| ≤ 10^6)\)

Output

• In ra số lượng xâu con đẹp của \(S\).

Example

abacaba
2
ba
cab

8

abacabaaabc
3
abaaca
cabbbb
c

15

Youtuber_TWK cho một cây gồm \(N\) đỉnh, đỉnh \(i\) có giá trị \(A_i\) và trọng số \(W_i\). Với mỗi cặp đỉnh phân biệt \({u, v}\), gọi \(P(u,v)\) là tích các giá trị \(A_x\) trên đường đi nối \(u\) và \(v\).
Cho số nguyên dương \(K\) (không phải số chính phương), cặp \({u,v}\) được gọi là tốt nếu \(P(u,v) = K·t²\) với \(t\) nguyên nào đó (tương đương: phần tự do chính phương của \(P(u,v)\) bằng phần tự do chính phương của \(K\)).

Với mỗi \(d\ =\ 0\ …\ N−1\), tính tổng \(∏\ W_x\) (theo mod \(998244353\)) trên tất cả các đường đi \({u,v}\) tốt có độ dài \(d\).

Input

• Dòng 1: hai số nguyên \(N,\ K\).
• Dòng 2: \(N−1\) số nguyên \(P_2,\ …,\ P_N\) (\(P_i\) là cha của đỉnh \(i\), \(1\ ≤\ P_i\ <\ i\)).
• Dòng 3: \(N\) số nguyên \(A_1,\ …,\ A_N\) (\(1\ ≤\ A_i\ ≤\ 10^6\)).
• Dòng 4: \(N\) số nguyên \(W_1,\ …,\ W_N\) (\(0\ ≤\ W_i\ <\ 998244353\)).

Constraints

• \(1\ ≤\ N\ ≤\ 120000\)
• \(1\ ≤\ P_i\ <\ i\)
• \(1\ ≤\ A_i\ ≤\ 10^6\)
• \(0\ ≤\ W_i\ <\ 998244353\)
• \(2\ ≤\ K\ ≤\ 10^6\), \(K\) là số tự do chính phương.

Output

• Một dòng gồm \(N\) số nguyên \(Ans[0],\ …,\ Ans[N−1]\), cách nhau bởi khoảng trắng.

Example

4 2
1 1 1
2 3 6 1
1 1 1 1

0 1 0 0

12 2
1 1 2 2 3 3 4 4 5 5 6
2 2 2 2 2 2 2 2 2 2 2 2
7 11 5 13 17 3 19 23 29 31 37 41

0 0 55118 0 9602791 0 86754360 0 0 0 0 0