Số học luôn là một lĩnh vực quyến rũ với các định lý đẹp, và đôi khi cũng nguy hiểm chết người. Có những tính chất ta nghĩ là dễ nhưng biến đổi thử mới thấy khó, nhưng đôi khi ngược lại, có những kết quả khá hiển nhiên mà ta thường tìm tòi những thứ rất xa xôi.

Do biết team ICPC của H3.2 cũng rất thích số học, đặc biệt là những bài đố mẹo, đố vui nên hôm nay, thầy Luna có giới thiệu một bài như sau: cho số nguyên dương ~n, m~, hỏi số ~n^{m!}~ thì chia cho ~2024~ dư mấy? Bạn hãy thử sức với bài toán đố vui này nhé.

Input

Một dòng duy nhất gồm hai số nguyên dương ~n, m~ với ~1 \le n, m \le 10^{18}~.

Output

Kết quả của bài toán.

Sample input 1

3 2

Sample output 1

9

Sample input 2

2023 100000

Sample output 2

1

Subtasks

• Có 25% test ứng với ~n, m \le 15~.
• Có 25% test ứng với ~m \le 15~.
• Có 50% test với giới hạn tùy ý.

Sau những ngày chinh chiến với CP, anh Phú về quê nghỉ dưỡng một thời gian và trồng hoa cùng chị. Vườn hoa của anh Phú có kích thước ~m \times n~ và trồng nhiều loại hoa có chiều cao nhất định. Nhưng vì vườn hơi rộng nên chị muốn chọn ra một phần trong vườn có kích thước ~h \times w~ để chăm sóc cho dễ, kịp đón Tết. Để phần vườn đó đẹp nhất, các cây hoa phải có chiều cao bằng nhau và Phú cần phải chọn ra một giá trị chiều cao ~x~ nào đó rồi thực hiện các thao tác: nếu trong phần vườn đang chọn, có hoa cao hơn ~x~ thì Phú sẽ đào đất sâu hơn để trồng cho hoa thấp vừa bằng ~x~; còn nếu hoa thấp hơn ~x~ thì Phú lại đắp đất cao hơn để hoa cao vừa bằng ~x~. Mỗi đơn vị chênh lệch chiều cao sẽ tốn của Phú thời gian không nhỏ, vì thế nên bạn sẽ chọn ra giá trị ~x~ để tiết kiệm công sức nhất có thể.

Biết Phú vất vả nên chị cũng muốn tính toán xem trong các cách chọn vị trí phần vườn thì giá trị ~x~ tương ứng có thể nhỏ nhất là bao nhiêu. Bạn hãy giúp chị trả lời câu hỏi này nhé.

Input

Dòng đầu tiên gồm 4 số nguyên ~m, n, h, w~ cho biết kích thước liên quan, trong đó ~1 \le h \le m \le 10^3~ và ~1 \le w \le n \le 10^3.~

Trong các dòng tiếp theo, ta có thông tin về chiều cao các bông hoa trong vườn chị, giá trị nguyên không âm và không vượt quá ~10^9.~

Output

Đáp số của bài toán.

Sample input

5 6 3 3
89 53 45 1 1 76
76 77 66 73 76 53
1 71 91 17 55 61
91 19 9 29 21 89
11 21 81 81 61 81

Sample output

21

Giải thích: ta có thể chỉ ra được nếu chọn phần vườn ~3 \times 3~ ở góc dưới bên trái thì giá trị ~x~ Phú sẽ chọn là ~21~, và chứng minh được số này là nhỏ nhất có thể.

Subtasks

• Có 20% số test có ~m, n ≤ 30~
• Có 20% số test có ~m, n ≤ 100~
• Có 30% số test có ~m, n≤ 300;~
• Có 30% số test có giới hạn như dữ kiện bài ra.

Lộc và Tài tuy ở chung phòng nhưng hay gửi thư cho nhau. Mỗi bức thư chỉ có viết 1 từ duy nhất viết bằng các chữ cái tiếng Anh in thường, nhưng có độ dài rất lớn. Thực ra mỗi từ đó có chứa một thông điệp ẩn giấu mà phải người trong cuộc mới có thể tìm ra được: thông điệp là một xâu đối xứng dài nhất có thể có trong bức thư, được tạo thành từ việc xóa đi một số ký tự gây nhiễu liên tiếp nào đó (bản chất là ghép một phần đầu và một phần cuối của bức thư lại với nhau).

Bạn cùng phòng của Lộc và Tài vừa tìm ra được danh sách ~n~ bức thư của họ, họ cũng nghe trộm được cách truyền tải thông điệp giữa hai bạn nên muốn ngồi giải mã ra từng thông điệp đó xem có gì hot không. Hỏi độ dài của các thông điệp tìm được là bao nhiêu?

Input

Dòng đầu tiên gồm số nguyên dương ~t~ với ~1 \le t \le 10^5~ là số bức thư. Trong ~t~ dòng tiếp theo, mỗi dòng là một từ duy nhất.

Output

Với mỗi bức thư, cho biết độ dài của thông điệp tìm được.

Sample input

5
a
abcdfdcecba
abbaxyzyx
codeisfun
acbba

Sample output

1
9
5
1
4

Giải thích Trong bức thư thứ hai, thông điệp cần tìm là ~abcdfdcba~, còn trong bức thư thứ ba, thông điệp cần tìm là ~xyzyx~.

Subtasks

Gọi M là tổng độ dài tất cả các xâu ~S~ trong mỗi test.

• Subtask 1 (50%): ~t≤1000,M≤5000~
• Subtask 2 (50%): ~t≤10^5,M≤10^6.~

Cho một cây gồm ~n~ đỉnh, các đỉnh được đánh số từ ~1~ tới ~n~, đỉnh 1 là gốc của cây. Trên mỗi đỉnh của cây lưu một số nguyên, ban đầu giá trị ở tất cả các đỉnh là ~0~. Bạn cần thực hiện ~q~ truy vấn thuộc một trong ba loại sau:

• add ~v~ ~k~ ~l~: Ta thay đổi giá trị các đỉnh thuộc cây con gốc ~v~ theo quy tắc sau:
  • Giá trị của đỉnh ~v~ được cộng thêm ~k~;
  • Giá trị các đỉnh là con trực tiếp của ~v~ được cộng thêm ~k-l~;
  • Giá trị các đỉnh là con trực tiếp của con trực tiếp của ~v~ cộng thêm ~k-2×l~;
  • Giá trị các đỉnh là con trực tiếp của con trực tiếp của con trực triếp của v được cộng thêm ~k-3×l~; các thao tác được thực hiện cho đến các nút lá của cây con gốc ~v~.
• get ~v~: tính giá trị của đỉnh ~v~.
• sum ~v~: tính tổng giá trị các đỉnh thuộc cây con gốc ~v.~ Yêu cầu: In ra kết quả các truy vấn loại 2 và 3 theo mô đun ~998244353.~

Input

• Dòng đầu tiên chứa số nguyên ~n~ với ~2≤n≤5×10^5~ là số đỉnh của cây.
• Dòng thứ hai chứa ~n-1~ số nguyên ~p_2,p_3,…,p_n~ với ~1≤p_i≤i-1~, trong đó ~p_i~ là cha trực tiếp của đỉnh ~i~.
• Dòng thứ ba chứa số nguyên ~q~ với ~1≤q≤5×10^5~ là số truy vấn cần thực hiện.
• Trong ~q~ dòng cuối cùng, mỗi dòng mô tả một truy vấn theo một trong ba định dạng add ~v~ ~k~ ~l~, get ~v~ hoặc sum ~v~ với ~1≤v≤n~ và ~0≤|k|,|l|≤2×10^9~.

Output

Với mỗi truy vấn loại 2 và 3, in ra một số nguyên không âm thể hiện kết quả của truy vấn theo mô đun ~998244353.~ Các số được viết trên một dòng của file dữ liệu vào/ra được ghi cách nhau bởi dấu cách.

Sample input

7
1 2 2 4 1 6 
11
add 1 5 1
get 1
get 2
get 3
get 4
get 5
get 6
get 7
add 4 7 3
sum 2
sum 6

Sample output

5 4 3 3 2 4 3 23 7

Subtasks

• Có 30% số test ứng với ~1≤n,q≤7000;~
• Có 25% số test ứng với có truy vấn loại 1 với ~l=0;~
• Có 25% số test khác không có truy vấn loại 3;
• Có 20% số test còn lại có giới hạn như dữ kiện bài ra.