Cho hai số nguyên dương ~n~ và ~k~.

Hãy tìm một hoán vị ~p~ của các số từ ~1~ đến ~n~ sao cho số lượng vị trí ~i~ thỏa mãn ~\gcd(p_i, i) = 1~ bằng đúng ~k~.

Yêu cầu

In ra một hoán vị ~p~ độ dài ~n~ thỏa mãn điều kiện trên. Nếu không tồn tại, in ra ~-1~.

Dữ liệu

Dòng duy nhất chứa hai số nguyên dương ~n~ và ~k~.

Kết quả

In ra trên một dòng:

• một hoán vị ~p_1, p_2, \dots, p_n~ thỏa mãn yêu cầu của bài toán; hoặc
• ~-1~ nếu không tồn tại.

Ví dụ

Ví dụ 1

Input

3 2

Output

2 1 3

Giải thích

Ví dụ 1

Với hoán vị ~p = [2, 1, 3]~:

• ~\gcd(p_1, 1) = \gcd(2, 1) = 1~
• ~\gcd(p_2, 2) = \gcd(1, 2) = 1~
• ~\gcd(p_3, 3) = \gcd(3, 3) = 3~

Có đúng ~2~ vị trí thỏa mãn ~\gcd(p_i, i) = 1~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le k \le n \le 10^6~

Chấm điểm

• Subtask ~1~ ~(20\%):~ ~n \le 10~
• Subtask ~2~ ~(80\%):~ Không có ràng buộc gì thêm

Cho một cây có ~n~ đỉnh, được gốc hóa tại đỉnh ~1~. Mỗi đỉnh được tô một trong hai màu: trắng hoặc đen.

Một cách tô được gọi là hợp lệ nếu với mọi đỉnh ~u~, trong cây con gốc ~u~, trị tuyệt đối của hiệu giữa số đỉnh trắng và số đỉnh đen không vượt quá ~1~.

Yêu cầu

Hãy đếm số cách tô hợp lệ của cây. In kết quả theo modulo ~998244353~.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~n~ — số đỉnh của cây.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~, biểu diễn một cạnh của cây.

Kết quả

In ra một số nguyên duy nhất là số cách tô hợp lệ của cây theo modulo ~998244353~.

Ví dụ

Ví dụ 1

Input

5
1 2
3 4
1 4
1 5

Output

12

Giải thích

Ví dụ 1

Có tất cả ~12~ cách tô màu thỏa mãn điều kiện đề bài.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 5 \times 10^5~

Chấm điểm

• Subtask ~1~ ~(20\%):~ ~n \le 20~
• Subtask ~2~ ~(20\%):~ ~n \le 10^3~
• Subtask ~3~ ~(20\%):~ ~n \le 10^5~
• Subtask ~4~ ~(20\%):~ ~n \le 3 \times 10^5~
• Subtask ~5~ ~(20\%):~ ~n \le 5 \times 10^5~

Cho hai xâu ~a~, ~b~ gồm các chữ cái Latin in thường. Xét dãy xâu ~f_1, f_2, \dots~ được xác định như sau:

• ~f_1 = a~
• ~f_2 = b~
• ~f_i = f_{i-2} + f_{i-1}~ với mọi ~i \ge 3~

Trong đó phép ~+~ là phép nối xâu.

Kí hiệu ~|S|~ là độ dài của xâu ~S~, và ~S_i~ là kí tự thứ ~i~ của ~S~.

Ban đầu và sau mỗi truy vấn cập nhật, dãy ~f~ luôn được xây dựng lại theo đúng quy tắc trên từ hai xâu hiện tại ~a~ và ~b~.

Yêu cầu

Xử lý ~q~ truy vấn thuộc một trong bốn loại sau:

• Loại ~1~: cho ~i, x~, hãy xác định kí tự ~f_i[x]~.
• Loại ~2~: cho ~i, l, r, \theta~, hãy đếm số lần kí tự ~\theta~ xuất hiện trong đoạn ~f_i[l \dots r]~.
• Loại ~3~: cho ~l, r, \theta~, gán mọi kí tự từ vị trí ~l~ đến ~r~ của xâu ~a~ thành ~\theta~.
• Loại ~4~: cho ~l, r, \theta~, gán mọi kí tự từ vị trí ~l~ đến ~r~ của xâu ~b~ thành ~\theta~.

Dữ liệu

• Dòng đầu tiên chứa xâu ~a~.
• Dòng thứ hai chứa xâu ~b~.
• Dòng thứ ba chứa số nguyên dương ~q~.

• ~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn theo một trong các dạng:

  • ~1\ i\ x~
  • ~2\ i\ l\ r\ \theta~
  • ~3\ l\ r\ \theta~
  • ~4\ l\ r\ \theta~

Ý nghĩa và ràng buộc của từng loại truy vấn:

• Truy vấn loại ~1~: ~1 \le i \le 10^{18}~, ~1 \le x \le \min(|f_i|, 10^{18})~

• Truy vấn loại ~2~: ~1 \le i \le 10^{18}~, ~1 \le l \le r \le \min(|f_i|, 10^{18})~, ~\theta~ là một chữ cái Latin in thường

• Truy vấn loại ~3~: ~1 \le l \le r \le |a|~, ~\theta~ là một chữ cái Latin in thường

• Truy vấn loại ~4~: ~1 \le l \le r \le |b|~, ~\theta~ là một chữ cái Latin in thường

Dữ liệu đảm bảo:

• ~1 \le |a|, |b| \le 10^6~
• ~1 \le q \le 10^5~

Kết quả

• Với mỗi truy vấn loại ~1~, in ra kí tự được yêu cầu.
• Với mỗi truy vấn loại ~2~, in ra số lần xuất hiện của kí tự tương ứng trong đoạn được hỏi.
• Các truy vấn loại ~3~ và ~4~ không cần in gì.

Ví dụ

Ví dụ 1

Input

abc
cb
6
1 5 11
2 4 2 7 b
3 1 2 d
4 2 2 c
1 5 9
2 6 7 18 c

Output

c
3
d
8

Giải thích

Ví dụ 1

• Truy vấn ~1\ 5\ 11~:

  Ta có ~f_5 = a + b + b + a + b = \texttt{abccbcbabccb}~. Kí tự thứ ~11~ của ~f_5~ là ~c~.

• Truy vấn ~2\ 4\ 2\ 7\ b~:

  Ta có ~f_4 = \texttt{cbabccb}~. Đoạn từ vị trí ~2~ đến ~7~ là ~\texttt{babccb}~, trong đó có ~3~ kí tự ~b~.

• Truy vấn ~3\ 1\ 2\ d~:

  Sau truy vấn này, xâu ~a~ trở thành ~\texttt{ddc}~.

• Truy vấn ~4\ 2\ 2\ c~:

  Sau truy vấn này, xâu ~b~ trở thành ~\texttt{cc}~.

• Truy vấn ~1\ 5\ 9~:

  Khi đó ~f_5 = \texttt{ddcccccddccc}~. Kí tự thứ ~9~ của ~f_5~ là ~d~.

• Truy vấn ~2\ 6\ 7\ 18\ c~:

  Ta có ~f_6 = \texttt{ccddcccddcccccddccc}~. Đoạn từ vị trí ~7~ đến ~18~ có ~8~ kí tự ~c~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le |a|, |b| \le 10^6~
• ~1 \le q \le 10^5~
• Với truy vấn loại ~1~ và ~2~, ~1 \le i \le 10^{18}~

Chấm điểm

• ~5%~ số test có ~|a|, |b| \le 16~, ~q \le 1000~, và với mọi truy vấn loại ~1~, ~2~ thì ~i \le 16~
• ~15%~ số test tiếp theo có ~|a|, |b| \le 1000~, ~q \le 1000~
• ~20%~ số test tiếp theo không có truy vấn loại ~3~ và loại ~4~
• ~20%~ số test tiếp theo thỏa mãn với mọi truy vấn loại ~3~ và loại ~4~ thì ~l = r~
• ~20%~ số test tiếp theo có ~|a|, |b| \le 10^5~
• ~20%~ số test còn lại không có ràng buộc gì thêm

Cho một cây có ~n~ đỉnh, gốc tại đỉnh ~1~. Mỗi đỉnh ~i~ có một màu ~c_i \in {0,1}~, và mỗi cạnh có một trọng số nguyên.

Xử lý ~q~ truy vấn thuộc một trong hai loại sau:

• ~1\ u~: đổi màu của đỉnh ~u~, tức là ~c_u := 1 - c_u~.
• ~2\ u\ v\ t\ k~: xét tất cả các đỉnh ~x~ nằm trong cây con gốc ~u~ và thỏa mãn ~c_x = t~. Hãy in ra ~k~ giá trị lớn nhất của độ dài đường đi từ ~v~ đến các đỉnh như vậy.

Đề bài đảm bảo trong mỗi truy vấn loại ~2~, có ít nhất ~k~ đỉnh ~x~ thỏa mãn điều kiện.

Yêu cầu

Với mỗi truy vấn loại ~2~, in ra ~k~ độ dài lớn nhất của các đường đi từ ~v~ đến những đỉnh ~x~ thuộc cây con gốc ~u~ có màu ~t~.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• Dòng thứ hai chứa ~n~ số nguyên ~c_1, c_2, \dots, c_n~, trong đó ~c_i \in {0,1}~ là màu ban đầu của đỉnh ~i~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i, v_i, w_i~, biểu diễn một cạnh nối hai đỉnh ~u_i~, ~v_i~ có trọng số ~w_i~.

• ~q~ dòng tiếp theo, mỗi dòng là một truy vấn thuộc một trong hai dạng:

  • ~1\ u~
  • ~2\ u\ v\ t\ k~

Kết quả

• Với mỗi truy vấn loại ~2~, in ra một dòng gồm ~k~ số nguyên là ~k~ độ dài lớn nhất cần tìm, theo thứ tự không tăng.
• Các truy vấn loại ~1~ không cần in gì.

Ví dụ

Ví dụ 1

Input

5 5
1 0 0 0 0
1 2 -1
2 3 2
4 3 1
3 5 -3
2 2 2 0 3
1 5
2 1 1 0 3
1 2
2 1 1 1 3

Output

3 2 0
2 1 -1
0 -1 -2

Giải thích

Ví dụ 1

Ban đầu, các đỉnh màu ~0~ là ~2, 3, 4, 5~.

• Truy vấn ~2\ 2\ 2\ 0\ 3~:

  Cây con gốc ~2~ gồm các đỉnh ~2, 3, 4, 5~. Các đỉnh màu ~0~ trong cây con này là ~2, 3, 4, 5~.

  Độ dài đường đi từ ~2~ đến các đỉnh đó lần lượt là:

  • đến ~2~: ~0~
  • đến ~3~: ~2~
  • đến ~4~: ~3~
  • đến ~5~: ~-1~

  Ba giá trị lớn nhất là ~3, 2, 0~.

• Truy vấn ~1\ 5~:

  Đổi màu đỉnh ~5~ từ ~0~ sang ~1~.

• Truy vấn ~2\ 1\ 1\ 0\ 3~:

  Các đỉnh màu ~0~ trong toàn cây là ~2, 3, 4~.

  Độ dài đường đi từ ~1~ đến các đỉnh đó là:

  • đến ~2~: ~-1~
  • đến ~3~: ~1~
  • đến ~4~: ~2~

  Ba giá trị lớn nhất là ~2, 1, -1~.

• Truy vấn ~1\ 2~:

  Đổi màu đỉnh ~2~ từ ~0~ sang ~1~.

• Truy vấn ~2\ 1\ 1\ 1\ 3~:

  Các đỉnh màu ~1~ trong toàn cây là ~1, 2, 5~.

  Độ dài đường đi từ ~1~ đến các đỉnh đó là:

  • đến ~1~: ~0~
  • đến ~2~: ~-1~
  • đến ~5~: ~-2~

  Ba giá trị lớn nhất là ~0, -1, -2~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n, q \le 10^5~
• ~c_i \in {0,1}~
• ~-10^9 \le w_i \le 10^9~

• Trong truy vấn loại ~2~:

  • ~1 \le u, v \le n~
  • ~t \in {0,1}~
  • ~1 \le k \le 3~
  • có ít nhất ~k~ đỉnh màu ~t~ trong cây con gốc ~u~

Chấm điểm

• Subtask ~1~ ~(20\%):~ ~n \le 10^4~
• Subtask ~2~ ~(15\%):~ Trong mọi truy vấn loại ~2~, ~u = v~
• Subtask ~3~ ~(25\%):~ ~w_i \ge 0~
• Subtask ~4~ ~(40\%):~ Không có ràng buộc gì thêm

Với một số nguyên dương ~x~, gọi:

• ~f(x)~ là tích các chữ số của ~x~
• ~g(x)~ là tổng các chữ số của ~x~

Số ~x~ được gọi là đẹp nếu:

• ~f(x) \ne 0~
• ~f(x)~ chia hết cho ~g(x)~

Yêu cầu

Cho ~T~ truy vấn. Với mỗi truy vấn gồm một số nguyên dương ~n~, hãy tìm một số đẹp có đúng ~n~ chữ số.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~T~ — số lượng bộ test.
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ — số chữ số của số cần tìm.

Kết quả

Với mỗi bộ test, in ra trên một dòng một số đẹp có đúng ~n~ chữ số.

Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Ví dụ

Ví dụ 1

Input

6
1
2
3
4
3
4

Output

9
63
167
6666
761
3789

Giải thích

Ví dụ 1

Các số trong phần output chỉ là một phương án hợp lệ.

• ~9~ có một chữ số, ~f(9) = 9~, ~g(9) = 9~, nên ~f(9)~ chia hết cho ~g(9)~.
• ~63~ có hai chữ số, ~f(63) = 18~, ~g(63) = 9~, nên ~18~ chia hết cho ~9~.
• ~167~ có ba chữ số, ~f(167) = 42~, ~g(167) = 14~, nên ~42~ chia hết cho ~14~.

Các dòng còn lại cũng là các số đẹp có đúng số chữ số yêu cầu.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le T \le 10^6~
• ~1 \le n \le 5 \times 10^6~
• Gọi ~N~ là tổng всех giá trị ~n~ trong toàn bộ input, dữ liệu đảm bảo ~N \le 5 \times 10^6~

Chấm điểm

• Subtask ~1~ ~(20\%):~ ~n \le 10~
• Subtask ~2~ ~(30\%):~ ~n = 2k + 1~ với một số nguyên không âm ~k~
• Subtask ~3~ ~(50\%):~ Không có ràng buộc gì thêm

Domino

Xét bảng ô vuông kích thước ~n \times m~, gồm ~n~ hàng và ~m~ cột. Các hàng được đánh số từ ~1~ đến ~n~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~m~ từ trái sang phải.

Ta chỉ xét các ô thuộc hình chữ ~L~ có độ dày ~2~, tức là các ô ~ (x, y) ~ thỏa mãn:

• ~1 \le x \le n~
• ~1 \le y \le m~
• ~x \le 2~ hoặc ~y \le 2~

Ngoài ra, có ~k~ ô bị chặn. Mỗi ô bị chặn đều thuộc hình chữ ~L~.

Một miếng domino ~1 \times 2~ có thể được đặt phủ đúng hai ô kề cạnh nhau theo hàng hoặc theo cột, và không được phủ lên ô bị chặn.

Yêu cầu

Hãy đếm số cách phủ kín toàn bộ các ô không bị chặn của hình chữ ~L~ bằng các miếng domino ~1 \times 2~. In kết quả theo modulo ~998244353~.

Dữ liệu

• Dòng đầu tiên chứa ba số nguyên ~n, m, k~.
• ~k~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~, biểu diễn một ô bị chặn.

Kết quả

In ra một số nguyên duy nhất là số cách đặt domino theo modulo ~998244353~.

Ví dụ

Ví dụ 1

Input

2 2 0

Output

2

Ví dụ 2

Input

3 3 1
1 1

Output

0

Giải thích

Ví dụ 1

Khi ~n = 2~, ~m = 2~, hình chữ ~L~ chính là toàn bộ bảng ~2 \times 2~. Có đúng ~2~ cách lát bảng bằng domino.

Ví dụ 2

Hình chữ ~L~ có ~8~ ô. Sau khi chặn ô ~ (1,1) ~ thì còn ~7~ ô không bị chặn, là số lẻ, nên không thể phủ kín bằng các miếng domino ~1 \times 2~.

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le n, m \le 10^9~
• ~0 \le k \le 10^4~

• Với mỗi ô bị chặn ~ (x, y) ~:

  • ~1 \le x \le n~
  • ~1 \le y \le m~
  • ~x~ và ~y~ không đồng thời lớn hơn ~2~

Chấm điểm

• Subtask ~1~ ~(20\%):~ ~n, m \le 10^6~
• Subtask ~2~ ~(40\%):~ ~k = 0~
• Subtask ~3~ ~(40\%):~ Không có ràng buộc gì thêm

Cho một lưới ~n \times m~ gồm ~n~ hàng và ~m~ cột. Mỗi ô thuộc một trong các loại sau:

• #: ô bị chặn
• .: ô trống
• S: vị trí ban đầu của người chơi
• B: vị trí ban đầu của thùng
• G: ô đích cần đưa thùng tới

Ban đầu có đúng một người chơi, đúng một thùng và đúng một ô đích.

Trong một bước, người chơi có thể di chuyển lên, xuống, trái hoặc phải sang một ô kề cạnh nếu ô đó nằm trong bảng và không bị chặn.

Nếu người chơi di chuyển vào ô đang chứa thùng, thì thùng sẽ bị đẩy theo cùng hướng, với điều kiện ô mới của thùng vẫn nằm trong bảng và không bị chặn.

Người chơi chỉ có thể đẩy thùng, không thể kéo thùng.

Yêu cầu

Với mỗi test, hãy xác định xem có thể đưa thùng từ vị trí ban đầu đến ô ~G~ hay không.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~T~ — số lượng test.

• Với mỗi test:

  • Dòng đầu tiên chứa hai số nguyên dương ~n, m~.
  • ~n~ dòng tiếp theo, mỗi dòng chứa một xâu độ dài ~m~ mô tả lưới.

Dữ liệu đảm bảo trong mỗi test:

• có đúng một kí tự S
• có đúng một kí tự B
• có đúng một kí tự G

Kết quả

Với mỗi test, in ra trên một dòng:

• YES nếu có thể đưa thùng đến ô ~G~
• NO nếu không thể

Không phân biệt chữ hoa, chữ thường.

Ví dụ

Ví dụ 1

Input

2
9 7
....##S
.##G...
....###
##..#..
##.##..
##B##..
#..##..
#..####
#..#...
9 7
....##S
###G...
....###
##..#..
##.##..
##B##..
#..##..
#..####
#..#...

Output

YES
NO

Giải thích

Ví dụ 1

• Ở test đầu tiên, tồn tại một dãy thao tác để đẩy thùng đến ô ~G~.
• Ở test thứ hai, chỉ khác test đầu tiên ở ô ~ (2,1) ~ bị chặn, và khi đó không thể hoàn thành nhiệm vụ.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le T \le 10~
• ~2 \le n, m \le 10^5~
• Trong mỗi test, ~n \times m \le 10^5~

Chấm điểm

• ~40\%~ số test có ~n \times m \le 1000~
• ~60\%~ số test còn lại không có ràng buộc gì thêm

Cho mảng số nguyên dương ~A_1, A_2, \dots, A_N~ và một số nguyên ~C~.

Xử lý ~Q~ truy vấn thuộc một trong ba loại sau:

• ~1\ l\ r\ v~: với mọi ~i~ thỏa mãn ~l \le i \le r~, gán ~A_i := A_i \cdot v~
• ~2\ l\ r\ v~: với mọi ~i~ thỏa mãn ~l \le i \le r~, gán ~A_i := A_i + v~
• ~3\ l\ r~: với mỗi ~K~ từ ~0~ đến ~4~, tính giá trị ~\displaystyle \sum_{x=l}^{r} \sum_{y=x}^{r} \left(C + \sum_{i=x}^{y} A_i\right)^K~ theo modulo ~10^9 + 7~

Yêu cầu

Với mỗi truy vấn loại ~3~, hãy in ra ~5~ số nguyên tương ứng với các giá trị khi ~K = 0, 1, 2, 3, 4~.

Dữ liệu

• Dòng đầu tiên chứa ba số nguyên ~N, Q, C~
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~

• ~Q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn thuộc một trong ba dạng:

  • ~1\ l\ r\ v~
  • ~2\ l\ r\ v~
  • ~3\ l\ r~

Kết quả

Với mỗi truy vấn loại ~3~, in ra một dòng gồm ~5~ số nguyên thuộc đoạn ~[0, 10^9 + 7)~, lần lượt là kết quả ứng với ~K = 0, 1, 2, 3, 4~.

Ví dụ

Ví dụ 1

Input

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

Output

1 20 400 8000 160000

Giải thích

Ví dụ 1

Ban đầu ~A = [4, 3, 3]~.

• Sau truy vấn ~1\ 1\ 3\ 4~, ta có ~A = [16, 12, 12]~
• Sau truy vấn ~2\ 1\ 3\ 4~, ta có ~A = [20, 16, 16]~

Ở truy vấn ~3\ 3\ 3~, chỉ có một đoạn con duy nhất là ~[3,3]~.

Khi đó:

• ~\sum_{i=3}^{3} A_i = 16~
• ~C + \sum_{i=3}^{3} A_i = 4 + 16 = 20~

Vì vậy, ~5~ giá trị cần in là:

• ~20^0 = 1~
• ~20^1 = 20~
• ~20^2 = 400~
• ~20^3 = 8000~
• ~20^4 = 160000~

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N, Q \le 10^5~
• ~0 \le C < 10^9 + 7~
• ~1 \le A_i < 10^9 + 7~

• Với truy vấn loại ~1~:

  • ~1 \le l \le r \le N~
  • ~1 \le v < 10^9 + 7~

• Với truy vấn loại ~2~:

  • ~1 \le l \le r \le N~
  • ~1 \le v < 10^9 + 7~

• Với truy vấn loại ~3~:

  • ~1 \le l \le r \le N~

Chấm điểm

Ngoài ra, bài có cơ chế chấm điểm riêng theo từng giá trị ~K~:

Lưu ý:

• Thí sinh không cần trả lời đúng đồng thời cho mọi giá trị ~K~ để được điểm.
• Ví dụ, nếu chỉ trả lời đúng với ~K = 0~ và ~K = 3~ trong nhóm ~N, Q \le 5 \times 10^4~, thì phần điểm nhận được là ~4% + 8%~ trong nhóm đó.
• Dù chưa giải đúng hết, ở mỗi truy vấn loại ~3~ thí sinh vẫn phải in ra đủ ~5~ số nguyên thuộc ~[0, 10^9 + 7)~.