Đây là bài để nhận giveaway 1 Miku plush rep 1:1 từ chúng mình.

Đề bài: Các bạn hãy đoán ba chữ số cuối cùng của kết quả Xổ số kiến thiết miền Bắc ngày 06/02/2025.

Thứ tự ưu tiên xếp giải sẽ như sau: Từ trùng khớp hoàn toàn ba chữ số cuối cùng của giải đặc biệt -> trùng khớp hoàn toàn ba chữ số cuối cùng của giải Nhất -> ... -> trùng khớp hoàn toàn hai chữ số cuối cùng của giải Bảy (với giải Bảy, chúng ta sẽ xét hai chữ số cuối cùng trong ba chữ số các bạn gửi lên hệ thống).

Nếu vẫn không tìm ra, sẽ lấy kết quả là số gần với ba chữ số cuối cùng của giải đặc biệt nhất. Nếu vẫn bằng nhau, bạn nộp sớm hơn sẽ được ưu tiên.

Mỗi lần đoán, các bạn hãy nộp chính xác ba chữ số vào bài này, chọn ngôn ngữ là TEXT. Cứ mỗi ~50~ điểm trong contest này, các bạn sẽ được nộp vào đây một lần, điều đó tương ứng với một cơ hội trúng giải. Nếu nộp quá số lần, các bạn sẽ bị loại khỏi giveaway. Chúng mình không thể xóa bài nộp của các bạn.

Ví dụ, bạn được ~497~ điểm trong contest, bạn sẽ được nộp vào đây tối đa ~9~ lần.

Chúc các bạn may mắn.

Mô tả về cách chơi. Ở trong hình, bạn hãy gõ số may mắn mà bạn chọn (ở đây là ~203~), sau đó bấm Nộp bài.

Đọc kỹ đề là chìa khóa dẫn tới thành công. Chỉ cần đọc đúng đề bài 1 VOI 2025, bạn đã có giải khuyến khích.

Nhân dịp Tết Ất Tỵ 2025, người người, nhà nhà đi chúc tết, Miku được tặng một bao lì xì may mắn.

Trong bao lì xì ấy, có một chút tiền và hai con số may mắn, có lẽ chúng mang những ý nghĩa nhất định với Miku.

Miku tự hỏi, một số nguyên bất kỳ, là ước chung của hai con số trên là bao nhiêu? Tuy nhiên, Miku đã quá quen với con số ~1~, nên cô ấy muốn tìm ra một con số khác. Các bạn hãy giúp Miku nhé!

Nhắc lại:

• Số nguyên ~d~ là ước của số nguyên ~x~ nếu tồn tại một số nguyên ~y~ mà ~d \times y = x~.

• Số nguyên ~d~ là ước chung của hai số nguyên ~x~ và ~y~ nếu ~d~ là ước của ~x~ và ~d~ là ước của ~y~.

INPUT

Dòng đầu tiên gồm số nguyên dương ~m~ (~1 \le m \le 10^{50}~).

Dòng thứ hai gồm số nguyên dương ~n~ (~1 \le n \le 10^{50}~).

OUTPUT

Một số nguyên khác ~1~, là một ước chung bất kỳ của cả ~m~ và ~n~. Nếu có nhiều kết quả, hãy in ra kết quả bất kỳ.

Có thể chứng minh luôn có kết quả với mọi ~m, n~ bất kỳ.

SAMPLE INPUT

2 
6

SAMPLE OUTPUT

2

SUBTASKS

Được biết, Miku là một người rất ham ăn, chính vì thế bây giờ người cô ấy tròn ung ủng và ai cũng chế nhạo ngoại hình của cô.

Chính vì thế, với mong muốn có một body người mẫu mà ai cũng ao ước, Miku buộc phải theo một chế độ giảm cân rất hà khắc như sau:

• Mỗi ngày, Miku chỉ được ăn tối đa ~k~ món.
• Mỗi món ăn, Miku chỉ ăn tối đa 1 lần một ngày.
• Vì bản chất ham ăn vốn có, mỗi ngày, Miku vẫn sẽ ăn nhiều món nhất có thể, nhưng vẫn phải đảm bảo trong chế độ cho phép và tiêu thụ ít kcal nhất.

Hiện tại, trong tủ lạnh của Miku đang có ~n~ các loại món ăn khác nhau, mỗi món ăn có giá trị kcal lần lượt là ~a_1, a_2, ..., a_n~, và số lượng từng món đang có là ~b_1, b_2, ..., b_n~. Nhiệm vụ của Miku rằng hãy thống kê số lượng món ăn còn lại sau một tuần theo chế độ? Được biết, trong thời gian này, Miku không được mua thêm thức ăn dự trữ, và cũng có thể nhịn nếu như trong tủ lạnh không còn đồ ăn.

INPUT

• Dòng đầu tiên nhập vào 2 số nguyên dương ~n, k~ (~n, k \le 10^5~) là số món ăn trong tủ lạnh và số món Miku có thể ăn tối đa mỗi ngày.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^9~) là số kcal của từng món ăn.
• Dòng thứ ba gồm ~n~ số nguyên dương ~b_1, b_2, ..., b_n~ (~b_i \le 10^9~) là số lượng của từng món ăn.

OUTPUT

• Dòng duy nhất in ra ~n~ số nguyên dương lần lượt là số lượng món ăn còn lại trong tủ lạnh của Miku sau một tuần ăn theo chế độ.

SAMPLE INPUT 1

5 5
1 2 3 4 5
7 7 7 7 7

SAMPLE OUTPUT 1

0 0 0 0 0

Giải thích: Mỗi ngày, Miku sẽ lần lượt ăn các món thứ ~1, 2, 3, 4, 5~ và ăn liên tục như thế trong vòng ~7~ ngày.

SAMPLE INPUT 2

5 1
1 2 3 4 5
7 6 5 4 3

SAMPLE OUTPUT 2

0 6 5 4 3

Giải thích: Mỗi ngày, Miku sẽ ăn món thứ ~1~ và ăn liên tục như thế trong vòng ~7~ ngày.

SAMPLE INPUT 3

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

SAMPLE OUTPUT 3

0 5 5 4 3

Giải thích: Trong 6 ngày đầu, mỗi ngày, Miku sẽ chỉ ăn món thứ ~1~. Tại ngày cuối cùng, Miku sẽ ăn món thứ ~2~.

SUBTASKS

Hôm nay là ngày 31 tháng 8 năm 2027 - cũng là ngày mà cô ấy quyết định tổ chức đám cưới với một cô gái tên R vào sinh nhật tròn 20 tuổi của cô.

Khác hẳn với Miku - một cô gái mười phần năng nổ, chín phần nghịch ngợm, thì R được biết đến là một người hơi ít nói, dễ xấu hổ và có phần "tsundere". Chính vì vậy, anh trai của R - tên là L lại có chút không yên tâm khi gả em gái R cho Miku.

Để L đồng ý cho Miku và R tổ chức đám cưới, thì hai người phải trả lời được bài toán mà L ra đề như sau:

Trên tay L đang có ~n~ con số, đảm bảo tất cả các số đều là số nguyên tố. Một số được định nghĩa là "số đẹp" nếu chúng là số nguyên dương, và chia hết cho ít nhất một con số mà L đang có.

Nhiệm vụ của Miku và R là đếm xem có bao nhiêu "số đẹp" thỏa mãn điều kiện của L mà các giá trị số thu được đều phải nhỏ hơn giá trị ~x~ cho trước.

Thời gian tổ chức đám cưới đang dần đếm ngược. Hãy giúp Miku và R giải bài toán trên để hai người có thể tổ chức lễ thành hôn đúng hạn nhé!

INPUT

• Dòng đầu tiên chứa hai số nguyên dương ~n~ (~n \le 25~) và ~x~ (~x \le 10^{18}~).
• Dòng thứ hai chứa ~n~ số nguyên tố ~a_1, a_2, ..., a_n~ (~a_i \le 10^{18}~).

OUTPUT

Dòng duy nhất là đáp số bài toán.

SAMPLE INPUT

2 10
3 7

SAMPLE OUTPUT

4

Giải thích: Các số thỏa mãn là ~3, 6, 7, 9~.

SUBTASKS

Do Miku mới tiếp xúc với tiếng Anh nên cô ấy đầy bỡ ngỡ, khi đọc bất cứ văn bản nào cô ấy cũng phải kè kè cuốn từ điển của mình để tra từ và tiện thể học luôn (Miku không có khái niệm tra từ điển điện tử vì Miku lowtech). Tất cả các từ trong từ điển đều được viết dưới dạng chữ latin viết thường.

Miku là một trong những người duy nhất biết tiếng Anh trong lớp (gọi là biết thôi chứ cũng chẳng giỏi), nên Miku rất hay được bạn bè trong lớp nhờ dịch hộ sang tiếng Việt. Hôm nay cũng chẳng là ngoại lệ với cô ấy! Một người bạn cùng bàn của Miku - tên là K, được biết do nay hỏng điện thoại không thể tự google translate những gì mà người yêu đến từ Anh viết cho anh ấy, nên quyết định nhờ Miku dịch hộ. Tất nhiên, với bản tính tốt bụng của mình, Miku vẫn sẽ chấp nhận lời đề nghị theo bản năng, nhưng khi Miku đọc lá thư, Miku nhận ra rằng ... hình như cô gái kia không biết viết cách từ ra! Từ nào từ nấy dính hết vào nhau, khiến người đọc từ xa sẽ có cảm tưởng rằng kia là lá thư kia bao gồm duy nhất một từ dài tầm 200 ký tự.

"Chậc, hôm nay sẽ vô cùng khó khăn với mình đây..."

Miku tặc lưỡi, tự nhiên muốn từ chối lời đề nghị này ghê nhưng lại bấm bụng làm vì lỡ miệng đồng ý. Như mọi khi, cô ấy vẫn sẽ mở cuốn từ điển và lần mò xem từ đó có ý nghĩa là gì rồi dịch lại cho K. Càng làm, Miku càng cảm thấy thử thách này khó hơn bản thân cô ấy tưởng rất nhiều! Chính vì thế, hãy giúp Miku tách các từ trong bức thư kia một cách rõ ràng, để Miku có thể tra từ thuận lợi hơn nhé. Nếu tồn tại cách tách sao cho tất cả các từ ta thu được đều tồn tại trong cuốn từ điển của Miku, cũng đồng nghĩa với việc bức thư đó có nghĩa và Miku hoàn toàn có thể dịch được bức thư. Nếu không tồn tại cách tách thỏa mãn, tức là bức thư kia hoàn toàn vô nghĩa.

Ví dụ: Từ điển của Miku có các từ như sau: noodles, i, love, hate, you.

Và bức thư có nội dung như sau: iloveyou, thì bạn phải tách thành i love you để Miku có thể dịch được.

Trường hợp khác, nếu nội dung bức thư là idontloveyou, tức là nội dung bức thư kia hoàn toàn vô nghĩa vì không tồn tại cách tách sao cho tất cả các từ đều có trong từ điển.

INPUT

• Dòng đầu tiên ghi ~2~ số ~n~ và ~q~ lần lượt là là số từ có trong từ điển của Miku và số bức thư mà K nhờ Miku dịch (~n \le 10^4, q \le 30~)
• ~n~ dòng tiếp theo, mỗi dòng gồm một từ trong từ điển (mỗi từ có tối đa ~20~ chữ cái). Tất cả các từ đều viết dưới dạng chữ latin viết thường.
• ~q~ dòng tiếp theo, mỗi dòng gồm một xâu là nội dung của từng bức thư mà K nhờ Miku dịch (mỗi bức thư có tối đa ~10^4~ ký tự). Tất cả các xâu đều được cấu tạo bởi chữ latin viết thường.

OUTPUT

• In ra ~q~ dòng, mỗi dòng in ra cách tách các từ sao cho tất cả các từ tách được đều phải xuất hiện trong từ điển của Miku. Nếu có nhiều cách tách thỏa mãn, hãy in ra một cách bất kỳ. Nếu không tồn tại cách tách thỏa mãn, in ra ~-1~.

SAMPLE INPUT

4 3
noodles
loves
miku
duong
noodleslovesmiku
duonglovesnoodles
noodleshatesmiku

SAMPLE OUTPUT

noodles loves miku
duong loves noodles
-1

SUBTASKS

Dạo này, Miku phát hiện ra cô ấy có sở thích đặc biệt với các con số. Nhân ngày sinh nhật, cô ấy được tặng một dãy số ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Ban đầu, tất cả các phần tử đều có giá trị bằng ~0~. Hôm nay, cô ấy quyết định đố các bạn cùng lớp bài toán như sau:

Miku có ~q~ phép màu biến tất cả các phần tử trong khoảng chỉ định ~[l, r]~ như sau: phần tử thứ ~l~ sẽ được tăng một giá trị ~1^2 \times x~, phần tử thứ ~l + 1~ sẽ được tăng một giá trị ~2^2 \times x~, phần tử thứ ~l + 2~ sẽ được tăng một giá trị ~3^2 \times x~, ..., phần tử thứ ~r~ sẽ được tăng một giá trị ~(r - l + 1)^2 \times x~.

Nhiệm vụ của các bạn là hãy tìm ra mảng ~a~ sau ~q~ lần hô biến của Miku.

INPUT

Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^7~).

Dòng thứ hai chứa số nguyên dương ~q~ (~1 \le q \le 10^7~) là số lượng truy vấn.

Dòng thứ ba gồm năm số nguyên dương ~l_1, l_2, r_1, r_2, x_{cap}~. (~1 \le l_1, l_2, r_1, r_2 \le 10^9~, ~1 \le x_{cap} \le 100~).

Các truy vấn sẽ được xây dựng như sau:

• Ban đầu, đặt ~cur_l = 0, cur_r = 0, cur_x = 0~.
• ~q~ truy vấn sẽ lần lượt được sinh ra bằng cách thực hiện lần lượt các thao tác như sau:
  • ~cur_l = (cur_l \times l_1 + l_2)~ ~\%~ ~n + 1~.
  • ~cur_r = (cur_r \times r_1 + r_2)~ ~\%~ ~n + 1~.
  • ~cur_x = (cur_x \times cur_l + cur_r)~ ~\%~ ~x_{cap} + 1~.
  • Nếu ~cur_l > cur_r~, ta đổi hai số này cho nhau.

Lúc này, truy vấn sẽ là bộ ba số (~cur_l~, ~cur_r~, ~cur_x~).

OUTPUT

Vì kết quả có thể rất lớn, hãy in ra tổng XOR của mảng ~a~, sau khi chia dư mọi phần tử cho ~10^9 + 7~.

Cụ thể hơn, hãy in ra ~(a_1~ ~\%~ ~(10^9 + 7))~ ~XOR~ ~(a_2~ ~\%~ ~(10^9 + 7))~ ~XOR~ ... ~XOR~ ~(a_n~ ~\%~ ~(10^9 + 7))~.

SAMPLE INPUT

5
4
1 2 3 4 7

SAMPLE OUTPUT

176

~XOR~ của cả mảng này là ~176~.

SUBTASKS

Hôm nay trong giờ học, vì bản tính thích mày mò của mình, Miku đã tạo ra một xâu "siêu đối xứng". Đó là xâu có độ dài chẵn, mà khi ta chia đôi xâu gốc thành hai phần bằng nhau, ta vẫn thu được hai xâu đối xứng có cùng độ dài.

Ví dụ, xâu aaaa là một xâu "siêu đối xứng" vì khi chia đôi, ta thu được hai xâu là aa và aa đều là xâu đối xứng. Xâu aab hay aaa không phải là xâu "siêu đối xứng" vì không thỏa mãn định nghĩa của Miku.

Miku đố bạn một bài toán như sau:

Cho xâu ~S~, với ~|S| \le 10^6~. Các chữ cái trong xâu ~S~ đều là các ký tự tiếng Anh viết thường. Hỏi tồn tại bao nhiêu xâu "siêu đối xứng" theo định nghĩa của Miku là xâu con liên tiếp của xâu S?

INPUT

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \le N \le 10^6~) là độ dài của xâu ~S~.
• Dòng thứ hai chứa xâu ~S~ chỉ có ký tự từ ~a~ đến ~z~.

OUTPUT

• In ra dòng duy nhất là đáp số bài toán.

SAMPLE INPUT 1

5
ababa

SAMPLE OUTPUT 1

4

Giải thích: Các xâu "siêu đối xứng" thu được là ab, ba, ab, ba

SAMPLE INPUT 2

5
aaaaa

SAMPLE OUTPUT 2

6

Giải thích: Các xâu "siêu đối xứng" thu được là aa, aa, aa, aa, aaaa, aaaa.

SUBTASKS

Mì là một cô gái nghiện Miku. Cô ấy có một đàn Miku nhồi bông được đặt ở trên giường ngủ cùng cô ấy, nhiều tới nỗi đôi khi cô ảo tưởng mình giống như mẹ Âu Cơ.

Khác hẳn với Mì, Dương lại chẳng ham hố gì mấy thứ này. Có những lúc, Dương đòi Mì dọn hết chỗ Miku mà cô ấy đặt trên giường đi sang nơi khác, để anh ấy có chỗ ngủ, và tất nhiên Mì không chịu. Dùng dằng ngày qua ngày, Dương cuối cùng cũng chịu hết nổi với Mì vì dường như lúc nào Mì cũng có tiếng nói cao hơn mình, Dương quyết định thách đố bằng cách ra câu đố như sau để thách Mì liệu có thông minh hơn anh ấy hay không.

Dương ký hiệu ~A[L...R]~ là số chỉ bao gồm các chữ số từ ~L~ tới ~R~ của ~A~. Ví dụ, với ~A = 200324~, thì ~A[4...6]~ ~=~ ~324~. Một số ~A~ có ~N~ chữ số được gọi là có chu kì ~K~ khi thỏa mãn tất cả các điều kiện sau:

• ~N~ chia hết cho ~K~.
• Với mọi ~1 \le i \le \frac {N}{K}~, ~A[((i - 1) \times K + 1)...(i \times K)]~ đều có giá trị bằng nhau.

Ví dụ:

• ~123123~ là số có chu kì ~3~ và ~6~.
• ~121212~ là số có chu kì ~2~ và ~6~.
• ~200324~ là số có chu kì ~6~.
• ~111111~ là số có chu kì ~1~, ~2~, ~3~ và ~6~.

Bài toán của Dương đưa cho Mì như sau:

Cho ba số nguyên dương ~L~, ~R~ và ~K~. Hãy tìm một số nguyên dương bất kì, không có các chữ số ~0~ không cần thiết ở đầu, mà ~\ge L~, ~\le R~ và có chu kì ~K~. Nếu không có số nào thỏa mãn, hãy in ra ~-1~.

Câu hỏi dường như rất hóc búa, Mì loay hoay mãi chưa giải được. Hãy giúp Mì trả lời câu hỏi trên, để đàn Miku của Mì không bị Dương đuổi đi!

INPUT

Dòng duy nhất gồm ba số nguyên dương ~L~, ~R~ và ~K~ (~1 \le L \le R \le 10^{5 \times 10^5}~, ~1 \le K \le 5 \times 10^5~).

OUTPUT

Dòng duy nhất là một số nguyên dương thỏa mãn đề bài.

Nếu có nhiều đáp án, in ra kết quả bất kì.

Nếu không có số nào thỏa mãn, in ra số ~-1~.

SAMPLE INPUT

200324 270923 2

SAMPLE OUTPUT

232323

SUBTASKS

Nay Dương ngẫm nghĩ lại, thấy đám Miku của Mì cũng xinh đấy chứ. Liếc nhìn đám Miku xinh xinh được Mì đặt gọn gàng trên chiếc giường bé nhỏ, tự nhiên Dương nhận ra bản thân mình cũng bị nghiện từ lúc nào không hay!

Cảm thấy bản thân hơi nặng lời, Dương quyết định xin lỗi Mì và hứa với Mì rằng chừng nào Mì chưa đủ 100 Miku, chừng đó Dương còn tặng Miku cho Mì. Thế là Mì - một cô gái dễ dãi - tha thứ Dương trong phút chốc!

Trong tháng vừa qua, Mì nhận ra ngày nào Dương cũng mua Miku cho mình - ít thì một con, nhiều thì năm con, nên Mì không thể nhớ nổi số lượng Miku mà Mì đang để trong nhà. Và cũng chính vì số lượng Miku tăng quá đột biến trong thời gian ngắn, Mì buộc phải dọn một phòng trống - và phòng này được đặt tên là "Miku's room". Đúng như tên gọi, đây là phòng chỉ dành cho đám con thơ của Mì (ý là đám Miku).

Mì và Dương quyết định xây những chiếc giá để Miku ở căn phòng này, chia thành các ô. Mỗi ô chỉ đặt duy nhất một Miku, được đánh số từ ~1~ đến ~10^n - 1~, không có các chữ số ~0~ không cần thiết ở đầu. Sau khi xem xét một lượt, Mì nhận thấy một quy luật khá thú vị như sau:

Những Miku được định giá là "Miku đắt tiền" đã được xếp vào các ô có chỉ số thỏa mãn tất cả các điều kiện:

• Có đúng ~n~ chữ số.
• Số lượng chữ số ~x~ nằm trong khoảng từ ~l~ tới ~r~.
• Số nhận được chia ~3~ dư ~k~.

Hãy giúp Mì đếm xem liệu Mì có bao nhiêu Miku được định giá là "Miku đắt tiền" nhé!

INPUT

Dòng duy nhất gồm năm số nguyên không âm ~n~, ~l~, ~r~, ~k~ và ~x~. (~1 \le n \le 10^{9}~, ~1 \le l \le r \le n~, ~r - l \le 10^4~, ~k \le 2~, ~x \le 9~).

OUTPUT

Dòng duy nhất là số lượng "Miku đắt tiền".

Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho ~10^9 + 7~.

SAMPLE INPUT

2 1 2 0 3

SAMPLE OUTPUT

6

Có ~6~ "Miku đắt tiền" là các Miku ở trong các ô ~30, 33, 36, 39, 63, 93~.

SUBTASKS