abcnickname và Cpascal trong một lần đi dạo chơi tình cờ thấy được một cái rương cũ kỹ. abcnickname quyết định mở ra xem thử trong đó có cái gì. Sau khi mở ra abcnickname thấy một tấm bản đồ kho báu cũ kỹ, vì nó khá cũ nên không thể nhìn thấy rõ chúng đang viết cái gì, chỉ có thể nhìn thấy các con số ngẫu nhiên và một cỗ máy enigma được cải tiến. Cpascal đã phát hiện ra rằng cỗ mãy đó có thể biên dịch các con số đó sang các đường đi nhưng thật không may. Để hoạt động thì cần phải có 5 mã code gồm 5 chữ số nhưng lại bị thiếu mất ~x~ mã code. abcnickname đã phát hiện ra rằng sau chiếc máy đó là một tờ giấy có chứa các gợi ý để tìm code và mở khóa máy đó mặc dù các gợi ý đó khá là mơ hồ nhưng sau một lúc thì abcnickname và Cpascal đã giải mã được các code đó để có thể sử dụng chiếc máy enigma

Dữ liệu vào:

• Là số code có được tối thiểu là 3 và tối đa là 4 (~3 ≤ x ≤ 4~)
• Sau đó lần lượt là vị trí mã code và mã code được sắp xếp tăng dần của vị trí mã code(được ngăn cách bằng dấu hai chấm ":")(ngoại trừ code bị thiếu)

Dữ liệu ra:

• Lần lượt là vị trí và mã code bị thiếu ngăn cách bởi dấu hai chấm (:)

Ví dụ:

Input: 01

4
1:12345
2:28967
4:11325
5:99812

Output: 01

3:57523

Input: 02

3
1:12345
2:28967
5:99812

Output: 02

3:57234
4:12943

Sau khi giải xong câu hỏi đó thì bất ngờ chiếc máy enigma đã dịch chuyển hai người abcnickname và Cpascal sang một mê cung khổng lồ với rất nhiều đường đi trước mặt họ là một bức tường gồm các ký tự như là (L , R) và một mảnh giấy trên tay abcnickname cũng là các ký tự đó nhưng ngắn hơn. Sau khi đọc qua và phân tích thì Cpascal đã biết được nguyên lý hoạt động của chúng bằng cách truy tìm các ký tự trên mảnh giấy đó và bức tường, tìm vị trí hợp lý, đánh dấu nếu là số chẵn thì là L còn lẻ thì R nhưng vì ký tự quá dài và thuật toán khá lâu và phức tạp vì vậy cần các bạn lập trình để có thể tạo ra được code tối ưu nhất, nhanh nhất để abcnickname và Cpascal có thể tiếp tục đi trước khi quá muộn và gặp những răc rối không mong muốn!

Yêu cầu: xuất ra số thứ tự cần rẽ đề abcnickname và Cpascal có thể di chuyển vào khu vực an toàn

Dữ liệu vào

• Đầu tiên là một xâu ~x~ là xâu ở trên tường với độ dài không quá 1000000 ký tự
• Thứ hai là một xâu ~y~ là xâu ở trong mảnh giấy đó dùng để so sánh xem chúng khớp một phần xâu ~x~ ở chỗ nào với độ dài không vượt quá ~x~ ký tự
• Và dữ liệu luôn luôn có đầu ra hợp lý không có trường hợp đặc biệt

Dữ liệu ra

• Tìm hiểu cách làm tối ưu của bài trên

Ví dụ

Input: 01

LLRRLRLRLLRRRLLRR
LLRR

Output: 01

L L R 

Input: 02

LLRRLRRRLRLLRLRLRLRLRLRRLLRRRLLRLLRLRLRLRLRRLRLRLR
LR

Output: 02

R L L R R R R R R R L R R R R R L L L 

Sau khi vượt qua được mê cung chết chóc đó abcnickname và Cpascal đã đến được vùng đất tình yêu, là nơi được hai người trị vì là công chúa và hoàng tử. Hai nhà thám hiểu của chúng ta bắt gặp được một khoảnh khắc rất là tình cảm đó chính là công chúa và hoàng tử đang hẹn hò, hai người ngồi hóng chuyện về tình cảm của hai người đó. Đang cao trào thì tự dưng chàng hoàng tử và cô công chúa gặp một vấn đề nhức nhối. Chàng hoàng tử vô tình gặp được abcnickname chàng hớn hở chạy lại kể lại sự việc như sau.

Được biết hoàng tử lại rất thích uống những ly rượu vang ở vị trí chẵn, còn công chúa thì ngược lại, cô công chúa này rất thích uống những ly ở vị trí chẵn. Nhưng vì hoàng tử là một người mắc hội chứng OCD nên cậu ta muốn mọi thứ là hoàn hảo nên đến việc uống rượu vang với người bạn đời của mình cũng như vậy, vậy thế nên phải nhờ đến hai nhà thám hiểm kiểm tra xem trên bàn có thể có những dãy ly nước liên tiếp sao cho số mililít rượu vang mà cả hai người sẽ uống là như nhau. Nhưng vì hai người chưa trải qua tình huống này bao giờ nên cần bạn giúp.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên dương t (~1 ≤ t ≤ 100~) - số lượng bộ test.
• Dòng tiếp theo chứa một số nguyên dương n (~1 ≤ n ≤ 2.10^4~) - số lượng ly nước.
• Dòng tiếp đó chứa n số nguyên dương a1, ..., an (~1 ≤ ai ≤ 10^7~) - số mililít nước của mỗi ly.

Dữ liệu ra

• Với mỗi bộ test, nếu có một dãy thỏa mãn yêu cầu đề bài thì in ra "YES" và "NO" nếu không tồn tại dãy như vậy.

Ví dụ

INPUT

2
3
1 6 5
6
2 6 1 5 7 8

OUTPUT

YES
NO

Sau khi giúp đỡ thì chàng hoàng tử đã chỉ dẫn đến khu vực kho báu abcnickname và Cpascal khá hứng hởi khi nghe được tin đó nhưng phía trước không phải là hoa hồng mà là một tòa tháp chọc trời được bao phủ bởi những tầng mây nhiệm vụ của hai người là làm sao để có thể leo lên đỉnh núi đó. Lần đầu tiên abcnickname đã thử đem toàn bộ món đồ có giá trị lên nhưng khi đem món cuối cùng thì đám mây lại sập khiến cho abcnickname bị ngã. Cú ngã đó khiến cho Cpascal phải suy nghĩ đám mây đó hoạt động như thế nào và chúng ra sao thì Cpascal phát hiện ra rằng mỗi đám mây chỉ có thể chịu được cân nặng của hai người và ~m~ cân nặng vậy cho nên Cpascal đã tính toán các đám mây để tìm ra được đám mây chịu tải nhỏ nhất, tính toán số cân nặng của chúng một cách tốt ưu nhất rồi sau đó mang chúng đi

Dữ liệu vào:

• Nhập một số nguyên ~n~ và ~q~ tương đương với số món đồ hiện tại và trọng lượng tốt đa mà mây yếu nhất chịu được(~1 ≤ n ≤ 200~)(~1 ≤ q ≤ 10^9~)
• Sau đó nhập ~a[n]~ tương đương với số cân nặng của đồ vật(~1 ≤ a[n] ≤ 10^8~)
• Sau đó nhập ~b[n]~ tương đương với giá trị của món đồ vật đó(~1 ≤ b[n] ≤ 10^8~)

Dữ liệu ra:

• Tổng giá trị của các đồ vật đó và số lượng đồ vật cần phải bỏ lại
• Lần lượt là từng món đồ vật bị bỏ lại và giá trị của chúng

Ví dụ

Input

3 8
3 4 5
30 50 60

Output

90
5 60

Sau khi cả nhóm leo lên được đỉnh của tòa tháp đó hai người cảm thấy rất vui và cũng rất mệt. Họ cảm thấy tiếc nuối với các đồ vật mà mình đã để lại nhưng không vì vậy mà họ lại bỏ cuộc, bỗng nhiên abcnickname đã nhìn thấy một căn phòng chỉ dẫn đến kho báu abcnickname hí hửng đi vào. Sau khi đi vào một cái rầm!!! abcnickname đã bị nhốt lại bên trong. Mặc dù hai người đã cố gắng nhưng cánh cửa không hề nhúc nhích buộc abcnickname phải tìm đường khác để đi. Khi khám phá căn phòng đó abcnickname đã phát hiện có ~n~ cái ghế gỗ, mỗi chiếc ghế được đánh dấu theo chiều kim đồng hồ và nhiệm vụ của abcnickname là phải tìm ra được chiếc ghế an toàn để có thể sống sót. Nhưng abcnickname chưa thể biết cách thức hoạt động của chúng là gì, và ra sao. Nhưng thật may mắn anh ấy có 4 lần quan sát để đoán xem quy luật của chúng, nhanh chống và dứt khoát nếu không lượt tiếp theo anh ấy có thể sẽ phải bỏ mạng tại đây!

Yêu cầu: lập trình sao cho có thể chọn được vị trí đúng

Dữ liệu vào

• Một số nguyên ~n~ tức nghĩa là số người tham gia(~10 ≤ n ≤ 10^6~)

Dữ liệu ra

• Một số nguyên tương đương với vị trí an toàn mà abcnickname cần phải ngồi

Ví dụ

Input: 01

10

Output: 01

5

Input: 02

5

Output: 02

3

Input: 03

25

Output: 03

19

Input: 04

100

Output: 04

73

Sau những lần gian nan và thách thức thì abcnickname và Cpascal cuối cùng cũng đã giải được câu đố đó nhưng thứ chờ đón họ tiếp theo lại là thử thách khốc liệt nhất mang tên aleph-zero ℵ₀. Không ép buộc cả hai nhà thám hiểm của chúng ta đã bị kẹt trong không gian dường như vô tận của aleph-zero. Dù có cố gắng đến mấy họ cũng không thể tài nào thoát khỏi chiều không gian chết tiệt đó cho đến khi có một cánh cửa xuất hiện. Vì không còn sự lựa chọn nào khác nên abcnickname và Cpascal phải bước vào cánh cửa đó. Bên trong chúng là hàng loạt các cánh cửa trải dài vô tận. Họ không biết nên chọn cánh cửa nào để đi. Họ đã thử mở từng cánh cửa thì họ mới phát hiện ra rằng khi có hai người mở các cánh cửa khác nhau thì những chiều không gian trong đó lại xuất hiện theo một cách trình tự nào đó mà hai nhà thám hiểm như chúng ta không thể hiểu nổi. Họ chỉ có thể dựa vào manh mối duy nhất đó chính là con số trên cánh cửa đầu tiên mà họ tiến vào kèm những ví dụ trên cánh cửa đó. Chúng có vẻ rất ít nhưng họ buộc phải suy nghĩ để có thể đoán được cánh cửa tiếp theo hoặc là họ sẽ mắc kẹt ở trong không gian này mãi mãi

Yêu cầu: tìm nguyên lý hoạt động và giải chúng

Dữ liệu vào

• Gồm một số nguyên ~n~ (~1 ≤ n ≤ 10^9~)

Dữ liệu ra

• Gồm hai số nguyên có lẽ là đáp án cho bày này.

Ví dụ

Input: 01

20

Output: 01

5 3

Input: 02

10

Output: 02

1 5

input: 03

1

output: 03

1 1

input: 04

2

output: 04

1 2

Sau hàng vạn lần tìm các cánh cửa thì hai nhà thám hiểm của chúng ta abcnickname và Cpascal cũng đã đến được khu vực cất giữ kho báu trong truyền thuyết. Trong kho báu đó là những món trang sức, đồ vật có giá trị rất cao abcnickname và Cpascal rất vui mừng thì bùm! Cả hai nhà thám tử của chúng ta đã bị dính bẫy của một bộ tộc skibidi toilet một bộ tộc gian xảo nhất. Hai nhà thám hiểm của chúng ta bị dính thuốc mê và đã ngủ một giấc ngủ 1 ngày(Đón xem chapter 02 nhé!)

Yêu cầu: nếu đã cố gắng giải được mấy bài chính thì xin chúc mừng nhé nhưng nên nhớ còn mấy bài sub-chapter khác còn chờ bạn nếu được thì hãy cố gắng làm nhé!(in ra 0)

Sau khi tiến vào mỗi người chia ra một đường để tìm tòi abcnickname chọn bên phải. Còn Cpascal thì chọn bên trái. Sau một lúc abcnickname đã tìm thấy cho mình một tấm bia kỳ lạ có khắc một cái hình rất giống mê cung trước đó mà abcnickname và Cpascal đã phải trải qua. Nhìn đi nhìn lại một hồi thấy có một ghi chú như sau "Lập trình robot, giải chúng, vượt qua các chứa ngại vật và tìm con đường tới đích nhanh nhất có thể" sau khi đọc qua luật chơi đó abcnickname chấp nhận thử thách. Anh ấy đã code 8 ngày 8 đêm. Sử dụng 8 chiếc máy tính và 800 năm học tin học để có thể giải được câu đố đó. Nhưng dù cố gắng đến đâu thì abcnickname chỉ có thể giải được 8 phần và phải nhờ bạn giải nốt 2 phần còn lại. Nếu được thì anh ấy sẽ rất cảm kích!

Yêu cầu: cho con robot tìm đường ngắn nhất có thể

Dữ liệu vào

Chỉ số của con robot như sau

• Và vị trí của chúng ~x~ và ~y~ (đảm bảo vị trí của con robot không trùng khớp với vị trí của bức tường)

Sau đó là kích thước của bản đồ gồm ~n~ x ~n~ (~10 ≤ n ≤ 100~) mỗi ô bản đồ cần phải điền như sau

• Nếu ô trống thì ghi ~0~
• Nếu ô tường thì ghi ~8~ (bức tường khiến robot không thể đi qua)
• Nếu là điểm kết thúc thì ghi ~9~ (điểm kết thúc có thể nằm ở bất cứ nơi nào!)
• Bắt buộc phải có lời giải và điểm kết thúc

Dữ liệu ra

• In ra chỉ số máu và số bước đi ngắn nhất!(Ưu tiên nước đi thay vì chỉ số máu)

Ví dụ

Input: 01

1 1
12 12
0 0 0 0 8 0 0 0 0 0 0 0 
8 8 8 0 8 0 8 8 8 8 8 0 
8 0 8 0 8 0 8 0 0 0 8 0 
8 0 8 0 8 8 8 0 8 0 8 0 
8 0 8 0 8 0 0 0 8 0 0 0 
8 0 8 0 8 0 8 8 8 8 8 0 
8 0 8 0 8 0 8 0 0 0 8 0 
8 0 8 0 8 0 8 0 8 8 8 0 
8 0 8 0 0 0 8 0 0 0 0 0 
8 0 8 8 8 8 8 0 8 8 8 8 
8 0 0 0 0 0 0 0 0 0 0 0 
8 8 8 8 8 8 8 8 8 8 8 9 

Output: 01

42

Đường đi của chúng

0 * * * 8 0 0 0 0 0 0 0 
8 8 8 * 8 0 8 8 8 8 8 0 
8 0 8 * 8 0 8 * * * 8 0 
8 0 8 * 8 8 8 * 8 * 8 0 
8 0 8 * 8 * * * 8 * * * 
8 0 8 * 8 * 8 8 8 8 8 * 
8 0 8 * 8 * 8 0 0 0 8 * 
8 0 8 * 8 * 8 0 8 8 8 * 
8 0 8 * * * 8 * * * * * 
8 0 8 8 8 8 8 * 8 8 8 8 
8 0 0 0 0 0 0 * * * * * 
8 8 8 8 8 8 8 8 8 8 8 9 

Vào một đêm nọ Cpascal có ra ngoài chút việc. Trên đường đi anh ấy thấy có một lâu đài cứ như là lâu đài bóng đêm vậy. Cpascal tò mò liên vào thử trong xem có gì thì bùm! Cánh cửa đã đóng lại khi Cpascal bước vào, anh ấy hoảng hốt và hoang mang không biết chuyện gì đang xảy ra cả. Thì tự dưng có một mụ phù thủy xấu xa bước tới và nói rằng "ngươi đã bị mắc kẹt ở lâu đài này rồi giờ ngươi muốn ra thì phải khiêu vũ với ta" Cpascal mặc dù cố gắng nhưng không tài nào có thể thoát ra được nên đành làm theo lời bà ta nói vậy. Sau khi bước vào khu vực khiêu vũ thì Cpascal mới biết được rằng khu vực khiêu vũ đó rất rộng rãi. Sàn nhà là hàng loạt ô vuông khi cộng chúng lại ta sẽ có ô vuông 5x5 mụ phù thủy nói rằng "đây là khu vực khiêu vũ. Để làm hài lòng ta đầu tiên ngươi cần chọn vào ô ngươi muốn, sau đó di chuyển theo cách mà con mã trong cờ vua nếu vị trí của con mã đó cao hơn so với con mã trước đó thì ta rất hài lòng, ưu tiên di chuyển tăng dần và tuyệt đối khi ngươi đã từng đi vào ô đó rồi thì ngươi sẽ không bao giờ có thể đi lại thêm một lần nữa. Lặp lại cho đến khi nào khiêu vũ hểt số ô trên sàn và ta đủ hài lòng ta sẽ thả ngươi ra" nói xong mụ phù thủy cho Cpascal một vài phút để suy nghĩ các nước đi làm sao khiến mụ phù thủy càm thấy hài lòng nhất mà không vi phạm điều trên

Rút gọn: cho một bàn cờ 5x5, bạn sẽ được chọn khu vực bạn muốn xuất hiện, mỗi nước đi đều sẽ giống như nước đi con mã, nếu vị trí ~x~ và ~y~ của con mã lớn hơn so với vị trí trước đó thì cộng 1 điểm, ưu tiên di chuyển tăng dần (ưu tiên y nhiều hơn x) nếu ô đó từng bước vào rồi thì không thể bước vào thêm lần nữa

Mục tiêu: in ra mức độ hài lòng cao nhất và sau đó là các nước đi.

Dữ liệu vào

• Vị trí của bạn lần lượt là ~x~ và ~y~

Dữ liệu ra

• Mức độ hài lòng
• Lần lượt là số thứ tự mà con mã có thể nhảy
• Các nước đi của mã không cần phải lấp đầy bàn cờ

Ví dụ

input: 01

1 1

output: 01

10
 1 12 19  4  0 
20  5  2 13 18 
 9 16 11  6  3 
 0 21  8 17 14 
 0 10 15 22  7 

input: 02

1 2

output: 02

10
16  1 20 13  0 
21  6 15  2 19 
10 17 12  7 14 
 5 22  9 18  3 
 0 11  4 23  8 

input: 03

3 3

output: 03

9
 5 20  9 14  0 
10 15  6 21  8 
19  4  1 16 13 
 2 11 18  7 22 
 0  0  3 12 17