📌 Lưu ý: Các bài được sắp xếp theo độ khó ngẫu nhiên, khuyến khích các bạn đọc hết tất cả các bài để tăng cơ hội xét giải cũng như tận hưởng trọn vẹn contest.

Vậy là rằm tháng Giêng đã đến. Theo truyền thống Việt Nam, các gia đình sẽ làm một mâm cúng với mong muốn "đầu xuôi đuôi lọt", cầu cho một năm mới an lành, vạn sự hanh thông và quốc thái dân an. Người xưa có câu "Lễ quanh năm không bằng Rằm tháng Giêng", bởi đây là thời điểm thiên địa giao hòa, khi ánh trăng tròn đầu tiên của năm mới rọi sáng mọi ngóc ngách, xua tan những tàn dư của năm cũ và đánh thức những mầm non hy vọng. Khắp các ngõ nhỏ, mùi nhang trầm phảng phất quyện vào không khí se lạnh còn sót lại của mùa xuân, tạo nên một không gian thành kính, nơi ranh giới giữa thực tại và tâm linh dường như chỉ cách nhau bằng một lời khấn nguyện.

Thời điểm này cũng là lúc Tết đã chính thức kết thúc. Những cành đào bắt đầu rụng cánh, màu đỏ rực rỡ của những tấm liễn đối đã nhuốm màu mưa bụi, và những phong bao lì xì cũng đã nằm yên trong ngăn kéo. Bữa cơm rằm thường là sự giao thoa cuối cùng giữa cái dư vị đậm đà của bánh chưng, giò chả và sự thanh tịnh của những món chay, như một lời chia tay nhẹ nhàng với những ngày hội xuân miên man. Mọi người bắt đầu dọn dẹp lại tâm thế, gói ghém những niềm vui đoàn viên vào một góc ký ức để sẵn sàng trở lại với nhịp sống hối hả của công việc và học tập.

Trên những nẻo đường, người ta không còn thấy những chuyến xe chở đầy hoa Tết, thay vào đó là dòng người tấp nập ngược xuôi với những dự định mới. Tết kết thúc không phải là sự khép lại của niềm vui, mà là sự chuyển hóa năng lượng từ những lời chúc tụng sang những hành động thực tế. Mỗi người đều mang theo một chút hơi ấm từ mâm cơm gia đình ngày Rằm để làm hành trang, bước vào một hành trình 365 ngày phía trước với tâm thế vững chãi nhất. Ánh trăng Nguyên Tiêu năm nay, vì thế, không chỉ là biểu tượng của sự viên mãn, mà còn là ngọn đăng tiêu soi đường cho những bắt đầu mới đầy triển vọng.

Đặc biệt, đối với các sĩ tử đang đứng trước ngưỡng cửa của những kỳ thi quan trọng, Rằm tháng Giêng không chỉ là một nghi lễ tâm linh, mà còn là hồi chuông báo hiệu cuộc đua nước rút thực sự đã bắt đầu. Ánh trăng tròn trịa ngoài kia như một lời nhắc nhở về sự vẹn toàn mà các bạn hằng mong ước sau bao ngày đèn sách. Gác lại những phong bao lì xì và những chuyến du xuân, đây là lúc bản lĩnh được mài giũa qua từng trang vở, từng đêm thức trắng để đổi lấy một tương lai rạng rỡ. Chúc các học sinh cuối cấp giữ vững tinh thần "vượt vũ môn", biến những áp lực thành động lực để chạm tay vào cánh cửa đại học hay cấp 3 mà các bạn mơ ước. Mong rằng khi mùa hạ tới, niềm vui của các bạn cũng sẽ tròn đầy và rạng rỡ như chính ánh trăng Nguyên Tiêu đêm nay.

Cũng liên quan tới rằm tháng Giêng, chắc hẳn, trong chương trình Văn của các năm học phổ thông, các bạn không còn xa lạ gì với bài thơ sau:

Kim dạ nguyên tiêu nguyệt chính viên,

Xuân giang xuân thủy tiếp xuân thiên.

Yên ba thâm xứ đàm quân sự,

Dạ bán quy lai nguyệt mãn thuyền.

Các bạn hãy in ra tác giả của bài thơ trên.

Input

Bài này không có input.

Output

In ra tác giả của bài thơ trên. Output cần được in ra viết liền, không dấu, không phân biệt chữ hoa / chữ thường.

Ông già Noel có ~n~ viên kẹo và dự kiến chia cho ~k~ bạn nhỏ. Vốn là một người cầu toàn, ông luôn tìm cách chia kẹo sao cho tất cả các bạn đều có kẹo. Đồng thời, số viên kẹo của các bạn phải cùng chẵn, hoặc cùng lẻ.

Hãy xác định xem ông già Noel có thể chia kẹo sao cho thỏa mãn yêu cầu trên không.

Input

Dòng duy nhất chứa hai số nguyên dương ~n~ và ~k~ (~1 \le n \le 10^9~, ~1 \le k \le 10^5~).

Output

In ra ~k~ số trên một dòng, số thứ ~i~ là số viên kẹo bạn thứ ~i~ nhận.

Nếu có nhiều phương án, in ra phương án bất kỳ.

Nếu không tồn tại phương án nào, in ra ~-1~.

Sample Input 1

5 3

Sample Output 1

1 3 1

Sample Input 2

3 2

Sample Output 2

-1

Sau ba năm cấp ba đầy sóng gió, thứ đọng lại trong lòng Huy không chỉ là một cô người yêu xinh xắn cùng lớp, mà còn là khoản tiền thưởng kếch xù từ kỳ thi Học sinh giỏi Quốc gia và nhiều kỳ thi khác nữa. Để giải trí với số tiền thưởng này, cậu ấy quyết định thiết kế ra một trò chơi.

Trên một con đường dài, cậu ấy chia thành ~n~ ô, từ trái sang phải được đánh số thứ tự từ ~1~ tới ~n~. Cậu ấy có ~d~ đồng tiền thưởng, và ban đầu cậu ấy đặt ~d~ đồng tiền thưởng này ở ô số ~1~.

Mỗi ô đều chứa một bóng đèn, ban đầu tất cả bóng đèn đều tắt. Tại bất kỳ thời điểm nào, nếu số đồng tiền thưởng ở ô thứ ~i~ đạt mức lớn hơn hoặc bằng ~a_i~, bóng đèn đó sẽ được bật sáng vĩnh viễn.

Trong mỗi giây, Huy có thể di chuyển một đồng tiền thưởng từ ô bất kỳ, sang ô liền trái hoặc liền phải. Huy sẽ chiến thắng nếu tất cả bóng đèn đều được bật sáng.

Yêu cầu: Hãy tính thời gian tối thiểu để Huy chiến thắng.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~d~ (~1 \le n \le 3 \times 10^5~, ~1 \le d \le 10^9~) là số ô trong trò chơi, và số đồng tiền thưởng của Huy.

Dòng thứ hai chứa ~n~ số nguyên không âm ~a_i~ (~0 \le a_i \le d~) là số đồng tiền thưởng tối thiểu để bật sáng bóng đèn ở từng ô.

Output

Thời gian tối thiểu để Huy chiến thắng.

Nếu Huy không thể chiến thắng, in ra ~-1~.

Sample Input

5 3
1 2 3 2 1

Sample Output

9

• Ban đầu, có ~3~ đồng tiền thưởng ở ô số ~1~, đồng thời, bóng đèn ở ô số ~1~ cũng được bật sáng luôn.
• Huy mất ~2~ giây để di chuyển ~2~ đồng từ ô số ~1~ sang ô số ~2~. Bóng đèn ở ô số ~2~ được bật sáng.
• Huy mất ~2~ giây để di chuyển ~1~ đồng từ ô số ~1~ sang ô số ~3~.
• Huy mất ~2~ giây để di chuyển ~2~ đồng từ ô số ~2~ sang ô số ~3~. Bóng đèn ở ô số ~3~ được bật sáng.
• Huy mất ~2~ giây để di chuyển ~2~ đồng từ ô số ~3~ sang ô số ~4~. Bóng đèn ở ô số ~4~ được bật sáng.
• Huy mất ~1~ giây để di chuyển ~1~ đồng từ ô số ~4~ sang ô số ~5~. Bóng đèn ở ô số ~5~ được bật sáng,

Huy mất ~9~ giây để chiến thắng trò chơi.

Cho ~Q~ truy vấn, mỗi truy vấn gồm một số thực.

Hãy cho biết số thực đó thuộc loại nào sau đây:

• lớn hơn ~0~.
• bằng ~0~.
• nhỏ hơn ~0~.

INPUT

Dòng đầu tiên là số nguyên dương ~Q~ (~1 \le Q \le 10^5~) là số truy vấn.

Mỗi truy vấn gồm một số thực ~x~ (~|x| \le 10^{18}~). Số ~x~ có thể có chữ số ~0~ không cần thiết ở đầu.

Dữ liệu đảm bảo tổng số lượng ký tự trong file input không vượt quá ~10^5~.

OUTPUT

~Q~ dòng, mỗi dòng là ~1~, ~-1~ hoặc ~0~, tương ứng lớn hơn ~0~, nhỏ hơn ~0~, hoặc bằng ~0~.

SAMPLE INPUT

4
3.58
-4.32
000.432
0.00

SAMPLE OUTPUT

1
-1
1
0

Dựa trên một câu chuyện sắp có thật ...

Cuối cùng thì kỳ thi ClueCup - sự kiện lớn nhất trong năm của ClueOJ đã diễn ra thành công. Giờ là lúc tính toán kết quả và trao giải.

Trong kỳ thi này, các thí sinh được cung cấp ~26~ bài tập, đánh số từ ~A~ đến ~Z~ để làm trong 300 phút. Mỗi bài tập có điểm số tối đa là ~100~. Sau ~300~ phút, đã có ~n~ bài nộp được gửi về hệ thống. Bài nộp thứ ~i~ gồm ~4~ tham số:

• ~name_i~ là xâu gồm tối đa ~10~ ký tự in thường, thể hiện tên người nộp.
• ~prob_i~ là một chữ cái in hoa, thể hiện bài tập trong lần nộp này.
• ~pen_i~ là một số nguyên tối đa ~299~, thể hiện penalty của bài này.
• ~points_i~ là một số nguyên tối đa ~100~, thể hiện điểm của bài này.

Các thí sinh sẽ được sắp xếp từ trên xuống theo thứ tự ưu tiên sau:

• Thí sinh nào có tổng điểm cao hơn sẽ xếp trên.
• Nếu hai thí sinh bằng điểm nhau, thí sinh nào có tổng penalty (penalty chỉ xét các bài có điểm dương) nhỏ hơn sẽ xếp trên.
• Nếu vẫn bằng nhau, ta coi hai thí sinh đó đồng hạng.

Điểm phạt, hay penalty của mỗi thí sinh sẽ được tính như sau:

• Penalty của một bài, là ~pen_i~ của lần nộp đầu tiên đạt điểm số tối đa trong bài đó, cộng thêm ~20~ nhân với số lần nộp trước lần nộp đó.

Ví dụ, một thí sinh có các lần nộp với cặp tham số ~[pen, points]~ như sau: ~[2, 10], [24, 20], [44, 90], [51, 50]~ sẽ có penalty là ~44 + 2 \times 20 = 84~.

Kỳ thi năm nay có ~m~ thí sinh, và ClueOJ sẽ trao huy chương vàng cho ~\lceil \frac {m}{10} \rceil~ thí sinh có thứ hạng cao nhất, nhưng không quá ~36~ thí sinh. Tuy nhiên, nếu hai thí sinh đồng hạng, hai thí sinh đó hoặc đều được trao huy chương vàng, hoặc đều không được trao huy chương vàng.

Nếu bài toán chỉ dừng lại ở việc tìm ra các thí sinh được huy chương vàng, thì đây sẽ là bài cơ bản. Vì vậy, thử thách dành cho các bạn như sau:

Bạn có thể thay đổi số điểm của tối đa một bài nộp. Hãy in ra các thí sinh có thể giành huy chương vàng.

Input

Dòng đầu tiên chứa số nguyên dương ~n, m~ (~1 \le n, m \le 10^5~) thể hiện số bài nộp và số thí sinh.

~n~ dòng tiếp theo, mỗi dòng gồm:

• Một xâu ~name_i~, có tối đa ~10~ ký tự in thường thể hiện tên của một thí sinh.
• Một ký tự ~prob_i~, là chữ cái in hoa thể hiện bài tập của lần nộp này.
• Một số nguyên ~pen_i~ (~0 \le pen_i \le 299~) thể hiện penalty của lần nộp này.
• Một số nguyên ~points_i~ (~0 \le points_i \le 100~) thể hiện điểm của lần nộp này.

Dữ liệu đảm bảo ~pen_1 \le pen_2 \le ... \le pen_n~.

Output

Với mỗi thí sinh có thể được huy chương vàng, hãy in ra trên một dòng. Các thí sinh cần được in ra theo thứ tự từ điển.

Sample Input

9 5
huy A 1 30
huy A 9 100
huy A 11 40
quang A 12 0
quang B 17 0
minhpk C 22 100
duong D 25 90
duong E 55 5
trinm A 60 75

Sample Output

duong
huy
minhpk
quang

Có tối đa 1 huy chương vàng.

Nếu ta không thay đổi bài nộp nào, minhpk sẽ đạt huy chương vàng với ~100~ điểm và penalty ~22~.

Nếu ta thay đổi bài nộp đầu tiên, cho huy được ~100~ điểm, huy sẽ đạt huy chương vàng với ~100~ điểm và penalty ~1~.

Nếu ta thay đổi bài nộp thứ tư, cho quang được ~100~ điểm, quang sẽ đạt huy chương vàng với ~100~ điểm và penalty ~12~.

Nếu ta thay đổi bài nộp thứ tám, cho duong được ~15~ điểm, duong sẽ đạt huy chương vàng với ~105~ điểm.

Cho ba số nguyên ~a~, ~b~ và ~c~.

Hãy so sánh ~a^c~ và ~b^c~.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 1000~) là số lượng test.

Với mỗi test, dòng duy nhất chứa ba số nguyên ~a, b, c~ (~1 \le |a|, |b| \le 10^3~, ~0 \le c \le 10^3~).

OUTPUT

Với mỗi test: in ra ~-1~ nếu ~a^c < b^c~, in ra ~0~ nếu ~a^c = b^c~, in ra ~1~ nếu ~a^c > b^c~.

SAMPLE INPUT

3
7 8 3
8 7 3
7 7 3

SAMPLE OUTPUT

-1
1
0

Ở đất nước Clue, một cửa hàng bán vải chỉ có bốn loại mảnh vải: loại 1 dài ~1~ mét, loại 2 dài ~3~ mét, loại 3 dài ~6~ mét, loại 4 dài ~7~ mét. Tất cả các mảnh vải đều có chiều rộng 1 mét.

Bạn cần mua chính xác ~n~ mét vải tại cửa hàng này. Hãy tìm số mảnh vải tối thiểu bạn cần mua.

Input

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 10^4~) là số lượng tests.

Mỗi test gồm một số nguyên dương ~n~ duy nhất (~1 \le n \le 363636^3~) thể hiện số mét vải bạn cần mua.

Output

~t~ dòng, mỗi dòng là số mảnh vải tối thiểu bạn cần mua.

Nếu không tồn tại cách mua thỏa mãn, in ra ~-1~.

Sample Input

2
10
14

Sample Output

2
2

Trong quá trình nghiên cứu các hệ thống mật mã dựa trên đặc trưng chữ số, các chuyên gia đã định nghĩa một lớp số nguyên đặc biệt gọi là số lõi kép.

Một số nguyên dương ~x~ được gọi là số lõi kép nếu:

• Gọi ~s(x)~ là tổng các chữ số của ~x~ trong hệ thập phân
• Gọi ~p(x)~ là tổng bình phương các chữ số của ~x~ trong hệ thập phân.
• ~x~ được gọi là số lõi kép nếu nó thỏa mãn điều kiện: $$x \pmod{s(x)^4 + p(x)^2} = 0$$

Cho ~T~ truy vấn, mỗi truy vấn gồm hai số nguyên ~L~ và ~R~, hãy đếm số lượng số lõi kép nằm trong đoạn từ ~L~ đến ~R~.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ (~1 \le T \le 10~) — số lượng truy vấn.
• ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L~ và ~R~ (~1 \le L \le R \le 2 \cdot 10^9~) mô tả một truy vấn.

Output

~T~ dòng, mỗi dòng chứa một số nguyên là kết quả của truy vấn tương ứng.

Sample Input

1
5 20

Sample Output

1

Chỉ có một số thỏa mãn là số ~10~, vì ~10~ chia hết cho (~1^4 + 1^2 = 2~).

Ngoài ra, số ~12002~ cũng thỏa mãn vì ~12002~ chia hết cho (~5^4 + 9^2 = 706~).

Đây là bài toán tương tác.

Dưới mái trường THPT chuyên C nọ, nhắc đến đội tuyển Tin học, không ai là không biết đến bộ đôi Dương và Huy. Khác biệt về cả tính cách lẫn phong cách gõ phím, nhưng họ lại là hai mảnh ghép hoàn hảo trên con đường chinh phục những thuật toán hóc búa nhất. Cùng với một người đồng đội nữa, cả hai đã viết nên lịch sử cho trường C khi mang về tấm huy chương Bạc ICPC National đầu tiên. Đó là một buổi sáng bùng nổ của cảm xúc, khi những dòng code chạy thâu đêm hôm nào cuối cùng cũng kết tinh thành quả ngọt, khẳng định vị thế của những cậu học trò trường C trên bản đồ lập trình thuật toán toàn quốc.

Thế nhưng, rũ bỏ ánh hào quang của những giải thưởng đồng đội, bước vào phòng đội tuyển, họ lại trở về làm những đối thủ "không đội trời chung". Bảng xếp hạng thi thử của trường chưa bao giờ có cơ hội đóng bụi ở vị trí top 1, bởi cái tên ngự trị trên đó liên tục được hoán đổi sau mỗi tối thứ Bảy. Dương và Huy cực kỳ nghiêm túc trong từng contest. Khoảng cách giữa họ thường chỉ được tính bằng một test case mỏng manh, hay một file code cầu may bị hệ thống trả về dòng chữ "Wrong Answer on test 4" đầy nghiệt ngã.

Cuộc đua tranh ấy không chỉ dừng lại ở tốc độ, mà còn là một màn đấu trí thuật toán đỉnh cao. Nếu Dương vừa hoàn thiện một cấu trúc dữ liệu hạng nặng, Huy sẽ mỉm cười bung ra một bộ test "anti-hash" hay những corner cases cực đoan để bẻ gãy bạn mình. Ngược lại, Dương cũng chẳng ngần ngại giăng ra những cái bẫy về tràn số hay bộ nhớ để ép Huy phải tối ưu thuật toán đến từng byte cuối cùng. Họ triệt hạ những sai lầm của nhau không khoan nhượng, không phải vì sự đố kỵ, mà vì họ ngầm hiểu với nhau một nguyên lý bất diệt của giới CP: thao trường đổ mồ hôi, chiến trường thi thật bớt rơi nước mắt.

Và rồi, ngày tàn khốc nhất cũng đến — kỳ thi Học sinh giỏi Quốc gia môn Tin học. Bầu không khí căng thẳng bao trùm, chỉ còn lại tiếng lạch cạch của bàn phím vang lên khô khốc. Cả hai đã chiến đấu với tất cả những gì mình có, vắt kiệt những ý tưởng tối ưu nhất. Bảng điểm công bố, cả trường C vỡ òa khi cả Dương và Huy đều xuất sắc giành Giải Nhì Quốc gia. Thế nhưng, ranh giới của vòng chọn đội tuyển Quốc tế lại quá đỗi khắc nghiệt. Nhờ một chút cẩn trọng hơn ở những test case cuối cùng — thứ mà cậu đã học được từ chính những lần bị Dương "bắt bài" trong phòng máy — Huy đã lách qua khe cửa hẹp, chính thức cầm trên tay tấm vé bước tiếp vào TST. Dương, dù tiếc nuối, đành gác lại giấc mơ vươn ra biển lớn năm ấy.

Chiều hôm đó, ánh nắng xiên ngang qua cửa sổ phòng máy quen thuộc. Không có những giọt nước mắt bi lụy, Dương chỉ vỗ vai Huy, một cái vỗ vai trao gửi cả những kỳ vọng dang dở. Kỳ thi Học sinh giỏi Quốc gia có thể đã khép lại, nhưng hành trình của họ thì chưa. Dù ai đi tiếp, ai dừng lại, cả hai đều biết rằng họ đã ghi danh thành công vào ngôi trường Đại học H danh giá. Ở đó, những bảng xếp hạng khốc liệt hơn, những thuật toán huyền bí hơn và cả một đấu trường ICPC sinh viên rộng lớn đang vẫy gọi. Bóng dáng hai người bạn thân lại bước đi song hành, sẵn sàng cho một chương mới, nơi họ sẽ không còn là đối thủ, mà mãi mãi là những người đồng đội ăn ý nhất.

Gác lại mọi bài vở, mọi thuật toán, họ lại tiếp tục gặp nhau tại một quán ăn quen thuộc trước ngày thi TST. Góc quán nhỏ nằm lọt thỏm giữa những tiếng còi xe hối hả, nơi chiếc bàn inox đã nhẵn bóng những vệt xước – bởi nó là chứng nhân cho không biết bao nhiêu cuộc tranh luận nảy lửa về độ phức tạp hay cách cài đặt của hai cậu học trò. Hôm nay không có những tiếng gõ phím lạch cạch, chỉ có hai cốc trà đá, ~n~ viên kẹo được xếp ngay ngắn trên mặt bàn, và một xấp tài liệu dày cộm được Huy mang theo với vẻ mặt đăm chiêu.

Nhắc đến TST, hay Kỳ thi chọn đội tuyển Quốc tế, ai trong giới CP cũng hiểu đó là một đấu trường hoàn toàn khác biệt. Nó không chỉ đòi hỏi nền tảng thuật toán siêu việt mà còn đánh đố thí sinh bằng những format mang đậm phong cách IOI: Interactive, Communication, hay Output Only. Và trớ trêu thay, đây lại chính là "lãnh địa" của Dương. Trong khi Huy xuất sắc ở sự cẩn trọng và độ ổn định trong các bài truyền thống, thì Dương lại sở hữu một tư duy cực kỳ quái gở và linh hoạt. Cậu là bậc thầy trong việc "lừa" grader, một kẻ săn điểm lẻ bằng các thuật toán Heuristic, và có một giác quan thứ sáu để tối ưu số lần truy vấn một cách đáng kinh ngạc.

Dù đã lỡ hẹn với tấm vé TST, Dương không mang trong mình nửa điểm chạnh lòng. Trên mặt bàn, cậu cẩn thận vẽ lại sơ đồ giao tiếp của một bài Communication lên chiếc iPad, kiên nhẫn giải thích cho thằng bạn thân từng tiểu tiết. Từ việc phải nhớ flush sau mỗi lần in kết quả để không dính lỗi Idleness limit exceeded, cho đến nghệ thuật phân bổ các bit chẵn lẻ để nén dữ liệu qua những hàm send() và receive().

"Mày nhớ nhé", Dương gõ nhẹ đuôi bút xuống bàn, giọng dứt khoát, "gặp bài Output Only thì đừng có húc đầu vào tìm thuật chuẩn ngay từ phút đầu. Cứ viết một cái Local Search thật mượt, chạy local lấy kết quả cắn subtask 1, subtask 2 đã rồi tính tiếp. Mày mà để trắng bài đó là tao nghỉ chơi với mày luôn đấy."

Huy im lặng lắng nghe, gật đầu ghi nhớ từng lời dặn dò. Trong ánh mắt của cậu không có sự kiêu hãnh của người chiến thắng vòng trước, cũng chẳng có sự ái ngại trước người bạn kém may mắn hơn mình. Huy biết, bước vào phòng máy TST ngày mai, cậu sẽ không chiến đấu một mình. Dương có thể không ngồi ở vị trí thí sinh, nhưng những chiến thuật "đào điểm" ma mãnh, những mẹo xử lý grader tinh quái của cậu sẽ hóa thành chiếc khiên vững chắc bảo vệ Huy trước những bộ test tàn nhẫn nhất. Bữa ăn kết thúc bằng một tiếng cụng ly giòn tan. Không cần những lời chúc sáo rỗng, chỉ có một cái gật đầu thật sâu và câu nói để lại của Dương trước khi quay xe: "Vào đó quậy tung cái server lên cho tao!"

Và đương nhiên, không còn gì tuyệt vời hơn kết thúc ngày ôn tập cuối cùng bằng một trò chơi trên những viên kẹo ấy ...

Trên bàn có ~n~ viên kẹo, ở mỗi lượt đi, người chơi được quyền bốc ~1, 2, 3, 4,~ hoặc ~5~ viên kẹo. Tuy nhiên, số kẹo bốc phải khác với số kẹo mà lượt đi liền trước nó đã được bốc. Người chơi nào không thể thực hiện lượt chơi của mình sẽ là người thua cuộc.

Bạn sẽ trong vai Huy, và bạn được quyền chọn đi trước hay đi sau. Hãy giúp Huy chiến thắng trò chơi này.

Tương tác

Đầu tiên, chương trình của bạn cần nhập số nguyên dương ~n~ (~1 \le n \le 1000~) từ đầu vào chuẩn.

Sau đó, chương trình của bạn cần in ra first hoặc second tương ứng bạn muốn đi trước hay đi sau.

Sau đó, trò chơi bắt đầu. Các lượt đi sẽ diễn ra luân phiên:

• Đến lượt bạn: Bạn cần in ra một số nguyên ~x~ (~1 \le x \le \min(5, \text{số kẹo còn lại})~) thể hiện số kẹo bạn muốn bốc. ~x~ phải khác với số kẹo mà đối thủ bốc ở ngay lượt trước đó (nếu có).
• Đến lượt máy chấm: Máy chấm sẽ in ra một số nguyên ~x~ tương tự như trên, hoặc ~-1~ nếu máy chấm nhận thua. Nếu máy chấm nhận thua, bạn cần kết thúc chương trình để nhận Kết quả đúng.

Nếu bạn nhận thua, bạn cần in ra ~-1~ và kết thúc chương trình.

Sau mỗi lần in dữ liệu, bạn cần flush dữ liệu để đảm bảo tương tác với máy chấm thành công.

Sample

Cho ba số nguyên dương ~n~, ~k~ và ~x~.

Hãy tìm chữ số tận cùng của ~1^{(x^k)} + 2^{(x^k)} + ... + n^{(x^k)}~.

Input

Dòng đầu tiên gồm số nguyên dương ~T~ (~1 \le T \le 10^4)~ là số truy vấn.

Mỗi truy vấn gồm ba số nguyên dương ~n~, ~k~, và ~x~ (~1 \le n, k, x \le 10^{18}~).

Output

~T~ dòng, mỗi dòng là chữ số tận cùng của biểu thức trên.

Sample Input

3
5 1 1
4 2 2
1 100 100

Sample Output

5
4
1

Một xâu được gọi là xâu đối xứng nếu đọc từ trái sang phải cũng giống như đọc từ phải sang trái. Ví dụ, A, ABA, ACCA là xâu đối xứng, còn AB thì không.

Cho một xâu ~s~ chỉ gồm các ký tự in thường, thực hiện hai loại truy vấn sau:

• ~1~ ~i~ ~c~: cập nhật ký tự ~s_i~ thành ~c~.
• ~2~ ~l~ ~r~: Tìm một xâu con liên tiếp bất kỳ trong đoạn ~[l, r]~ của ~s~ thỏa mãn xâu đó là xâu đối xứng. Nói cách khác, tìm hai chỉ số ~u, v~ (~l \le u \le v \le r~) thỏa mãn ~s[u...v]~ là xâu đối xứng.

INPUT

Dòng đầu tiên gồm số nguyên dương ~n~ và ~q~ (~1 \le n, q \le 3 \times 10^5~) - độ dài xâu ~s~ và số truy vấn.

Dòng thứ hai gồm xâu ~s~ chỉ gồm các ký tự in thường. Lưu ý, các ký tự trong xâu được đánh số từ ~1~.

~q~ dòng tiếp theo, mỗi dòng thể hiện một truy vấn:

• ~1~ ~i~ ~c~ mô tả truy vấn loại 1 (~1 \le i \le n~, ~c~ là ký tự in thường).
• ~2~ ~l~ ~r~ mô tả truy vấn loại 2 (~1 \le l \le r \le n~).

OUTPUT

Với mỗi truy vấn loại ~2~, in ra hai chỉ số ~u, v~ (~l \le u \le v \le r~) thỏa mãn đề bài. Nếu không có chỉ số nào thỏa mãn, in ra ~-1~.

SAMPLE INPUT

5 4
abcdd
2 1 5
1 5 e
1 3 a
2 1 4

SAMPLE OUTPUT

4 5
1 3

Cho dãy số nguyên dương ~a~ gồm ~n~ phần tử.

Ta gọi ~V~ là tích tất cả các phần tử của dãy ~a~.

Hãy tìm số nguyên dương ~x~ nhỏ nhất, sao cho ~V~ không chia hết cho ~x~.

Input

Dòng đầu tiên chứa số nguyên dương ~T~ (~1 \le T \le 10^5~) là số bộ tests. Mỗi bộ test gồm:

• Dòng đầu tiên gồm số nguyên dương ~n~ (~1 \le n \le 10^5~) - số phần tử của dãy.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_i~ (~1 \le a_i \le 10^5~) - các phần tử của dãy.

Dữ liệu đảm bảo ~\sum n \le 10^5~.

Output

Với mỗi test, in ra số nguyên dương ~x~ nhỏ nhất, sao cho ~V~ không chia hết cho ~x~.

Lưu ý, kết quả có thể vượt quá ~10^{18}~.

Sample Input 1

2
5
4 3 2 4 6
4
2 10 14 4

Sample Output 1

5
3

Trong test 1, ~5~ là số nhỏ nhất mà ~576~ không chia hết.

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

Hãy xây dựng một dãy số có nhiều phần tử nhất, giả sử dãy có ~x~ phần tử, dãy cần thỏa mãn:

• ~\sum a_i = n~.
• ~a_i > 0~.
• Không có tập con nào của dãy có tổng bằng đúng ~k~.

Input

Dòng đầu tiên chứa số nguyên dương ~T~ (~1 \le T \le 200~) là số lượng test.

Mỗi test gồm hai số nguyên dương ~n, k~ (~1 \le n \le 10^{18}, 1 \le k \le 8~).

Output

~T~ dòng, mỗi dòng là số phần tử lớn nhất tìm được.

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

Sample Input

3
5 2
7 3
8 1

Sample Output

2
3
4

Trong test đầu tiên, dãy là ~[1, 4]~.

Trong test thứ hai, dãy là ~[1, 1, 5]~.

Trong test thứ ba, dãy là ~[2, 2, 2, 2]~.

Cho bảng kích thước ~n \times m~, ô ở hàng ~i~, cột ~j~ có chứa số nguyên dương ~a_{i, j}~. Trên bảng, bạn chỉ có thể di chuyển xuống dưới hoặc sang phải.

Xét một cặp số ~(l, r)~. Khi đó, cặp số ~(l, r)~ được gọi là hợp lệ nếu: chỉ xét các ô có chứa giá trị trong đoạn ~[l, r]~, bạn có thể sử dụng các ô đó để di chuyển từ ô ~(1, 1)~ tới ô ~(n, m)~.

Ví dụ:

• Xét bảng sau:

1 2 3
3 2 1

• ~(1, 2)~ là một cặp số hợp lệ vì ta có thể di chuyển như sau: ~(1, 1) - (1, 2) - (2, 2) - (3, 2)~.
• ~(2, 3)~ không là cặp số hợp lệ vì ta không thể di chuyển.

Hãy đếm số lượng cặp số ~(l, r)~, thỏa mãn ~1 \le l \le r \le max (a)~, và cặp số đó là hợp lệ. ~max (a)~ ở đây là giá trị tối đa trên bảng ~a~.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n, m~ (~1 \le n \le 5~, ~1 \le m \le 10^5~) mô tả kích thước bảng.

~n~ dòng tiếp theo, mỗi dòng gồm ~m~ số nguyên dương ~a_{i, j}~ (~1 \le a_{i, j} \le 10^9~) mô tả một ô trên bảng.

Output

In ra số cặp số thỏa mãn điều kiện.

Sample Input

2 3
1 2 3
3 2 1

Sample Output

2

Hai cặp số thỏa mãn là ~(1, 2)~ và ~(1, 3)~.

Hôm nay, em gái của Bob - tên Alice, vừa tròn bảy tuổi. Chính vì thế, hôm nay, Bob quyết định "tặng" một món quà sinh nhật rất ý nghĩa với Alice - chính là dạy em mình cách tính tổng các số trong phạm vi 100.

Thế nhưng, để bài học đỡ nhàm chán hơn, anh sẽ biến bài giảng của mình thành một tiết có thể vừa chơi, vừa học. Bob cho Alice một chiếc bảng như sau:

Khi anh hô bốn giá trị (với hai giá trị đầu (~i, j~) là tọa độ góc trái trên của bảng con, và (~k, l~) là tọa độ góc phải dưới của bảng con), thì Alice phải tính tổng tất cả các giá trị trong bảng con từ dữ kiện mà anh trai mình cho trước. Ví dụ: Nếu Bob muốn tìm giá trị từ (~1, 1~) đến (~3, 3~) thì Alice phải đưa đáp án là ~108~ (vì ~1 + 2 + 3 + 11 + 12 + 13 + 21 + 22 + 23 = 108~).

Chơi với Alice một hồi, Bob nhận ra rằng bài toán này có thể xây dựng dưới dạng tổng quát. Bài toán ấy như sau:

Cho một bảng có kích thước ~m \times n~, đánh số từ 1 đến ~m \times n~ theo thứ tự lần lượt từ trái sang phải, từ trên xuống dưới. Alice có ~q~ lượt chơi. Với mỗi lượt chơi, Bob sẽ đưa ra 4 số ~i, j, k, l~ với (~i, j~) là tọa độ góc trái trên của bảng con, và (~k, l~) là góc phải dưới của bảng con. Nhiệm vụ của Alice là với mỗi lượt chơi, cô phải đưa ra chính xác tổng tất cả giá trị trong bảng con từ dữ kiện mà anh trai mình cho trước.

Input

• Dòng đầu tiên nhập vào hai số nguyên dương ~m, n~ (~1 \le m, n \le 10^9~) với ~m~ là số hàng của bảng, ~n~ là số cột của bảng.
• Dòng tiếp theo nhập vào số nguyên dương ~q~ (~1 \le q \le 10^6~).
• ~q~ dòng tiếp theo, mỗi dòng bao gồm bốn số ~i~ ~j~ ~k~ ~l~ (~1 \le i \le k \le m~, ~1 \le j \le l \le n~), với (~i, j~) là tọa độ góc trái trên của bảng con, và (~k, l~) là góc phải dưới của bảng con.

Output

Để giảm kích thước đầu ra:

• Gọi ~ans_i~ là đáp án của Alice đưa ra khi chia dư cho ~10^9 + 21~.
• Hãy in ra ~ans_1~ ~XOR~ ~ans_2~ ~XOR~ ~ans_3~ ~XOR~ ... ~XOR~ ~ans_q~.

Sample Input

10 10
2
1 1 3 3
2 2 2 3

Sample Output

117

Giải thích: Ở ví dụ thứ hai, Alice sẽ tính ~12 + 13 = 25~.

huyhau6a2 là một trong những thành viên của ban ra đề cho kỳ thi Codeforces Round 3636 (Div. 1 + 2), và cậu được chọn là người ra bài toán dễ nhất cho kỳ thi. Sau khi chuẩn bị xong, việc còn lại của huyhau6a2 là bảo mật đề thật tốt trước khi kỳ thi diễn ra. Tuy nhiên, thông tin về việc huyhau6a2 sẽ ra đề bằng cách nào đó đã bị tuồn ra, đã có rất nhiều người nhận thấy họ có thể ăn cắp đề để bán lấy tiền hoặc giữ lại để chuộc lợi cho bản thân. Vì thế nên họ đã tìm đủ mọi cách để xác định vị trí và đột nhập vào nơi giấu đề của huyhau6a2.

Biết trước được điều này, huyhau6a2 đã tạo ra một hệ thống bảo mật để bảo vệ đề thi trong ~q~ ngày sắp tới trước khi Codeforces Round đó bắt đầu. Bất kỳ ai không phải là người trong ban ra đề mà muốn truy cập vào đề thi của huyhau6a2 đều phải nhập mật khẩu. Đó là một mã số gồm ~n~ ký tự, mỗi ký tự có thể là một chữ số từ ~0~ đến ~9~. Hệ thống bảo mật đặc biệt cho phép mỗi ngày reset lại mật khẩu đúng, điều này giúp chỉ những người có quyền mới có thể truy cập một cách nhanh chóng. Đồng thời, hệ thống còn có một tính năng cho phép người nhập mật khẩu chỉ cần nhập một đoạn các ký tự từ ~l~ đến ~r~ của mật khẩu thay vì nhập hết, điều này làm giảm thời gian để nhập mật khẩu nhưng không ảnh hưởng nhiều đến tính bảo mật của đề thi. Giá trị ~l,r~ này được cố định trong suốt một ngày và sẽ reset lại vào ngày tiếp theo, khi nhập thì người nhập được biết trước hai giá trị này để có thể xác định chính xác đoạn mật khẩu cần phải nhập.

Với những người có quyền truy cập thì họ chỉ cần quét thẻ đặc biệt trong ~3.6~ giây thì đã có thể truy cập vào đề thi của huyhau6a2. Tuy nhiên với những người khác thì họ sẽ cần thời gian để đoán và nhập mật khẩu. Giả sử bạn - một người mới vô hệ thống để nhập mật khẩu, bạn có thể thực hiện một trong hai hành động sau đến khi hệ thống mở khóa:

• Nhập mật khẩu: Bạn nhập mật mã tương ứng với đoạn ký tự ~[l,r]~ của mật khẩu và hệ thống sẽ trả về mật mã mà bạn vừa nhập đúng hay sai, ngoài ra thì hệ thống không trả về gì thêm. Hành động này mất ~1~ đơn vị thời gian.
• Gợi ý mật khẩu: Bạn được phép chọn một ký tự ~i\ (l\le i\le r)~ và bạn sẽ biết được luôn giá trị của ký tự thứ ~i~ của mật khẩu. Tuy nhiên hành động này sẽ mất ~t_i~ đơn vị thời gian do hệ thống phải truy cập vào đám mây và còn nhiều yếu tố khác nữa để có thể trả về chính xác ký tự đó. Các giá trị ~t_i~ này là cố định và sẽ không bao giờ thay đổi theo ngày hay bất kỳ yếu tố nào khác.

Tuy hệ thống đã rất hoàn thiện nhưng huyhau6a2 muốn biết hệ thống của mình có thể bảo mật tốt trong ~q~ ngày sắp tới không. huyhau6a2 tin rằng nếu thời gian để một người mò mật khẩu càng lâu thì hệ thống bảo mật của mình càng mạnh. Vì thế nên huyhau6a2 đã viết một chương trình giúp xác định nhanh thời gian tối thiểu để một người mò mật khẩu từ đầu có thể truy cập vào đề thi của mình. Cảm thấy vấn đề này rất thú vị nên huyhau6a2 cũng muốn đem bài toán này ra để mọi người cùng thử sức, liệu các bạn có thể giải quyết bài toán hóc búa này không?

Trong bài toán này chúng ta chỉ giả định trường hợp từ khi một người bắt đầu mò mật khẩu đến khi truy cập vào được đề thi thì hệ thống không reset lại sang ngày mới, tức là giá trị ~l,r~ và các dữ liệu nhập mật khẩu trong suốt quá trình nhập sẽ ổn định và không thay đổi đến khi người đó nhập mật khẩu thành công.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~q~ tương ứng với độ dài của mật khẩu và số ngày trước khi Codeforces Round diễn ra ~(1\le n,q\le 2\times 10^5)~.

Dòng thứ hai gồm ~n~ số nguyên ~t_1,t_2,\dots,t_n~ tương ứng với thời gian để hệ thống gợi ý ký tự thứ ~1,2,\dots,n\ (0\le t_i\le 10^9)~.

Dòng thứ ~j~ trong ~q~ dòng cuối cùng gồm hai số nguyên dương ~l_j,r_j~ tương ứng với đoạn ký tự ~[l_j;r_j]~ cố định của mật khẩu cần phải nhập trong ngày thứ ~j~ ~(1\le j\le q,1\le l_j\le r_j\le n)~.

Output

In ra ~q~ dòng, dòng thứ ~j~ gồm duy nhất một số nguyên là thời gian tối thiểu để một người có thể truy cập vào đề thi nếu muốn truy cập vào ngày thứ ~j~.

Sample Input

6 2
0 1 6 7 1 1
6 6
1 2

Sample Output

1
1

Một số tự nhiên ~x~ được gọi là may mắn nếu:

• Gọi ~f(x)~ là tổng các chữ số của ~x~, ~g(x)~ là tích các chữ số của ~x~.
• Lúc này, ~x~ cần thỏa mãn: $$f(x) = \frac {g(x)}{2} = \frac {x}{4}$$

Hãy đếm số lượng số may mắn trong đoạn từ ~l~ tới ~r~.

Input

Hai số tự nhiên ~l~ và ~r~ (~0 \le l \le r \le 10^{18}~).

Output

Số lượng số thỏa mãn.

Sample Input

20 40

Sample Output

1

Chỉ có một số thỏa mãn là ~36~.

Năm 2036, bạn là kỹ sư trưởng của trạm vũ trụ Clue. Trạm sở hữu một dải pin năng lượng gồm ~n~ lõi được xếp thành một hàng ngang, đánh số từ ~1~ đến ~n~. Mỗi lõi mang một mức năng lượng là một số nguyên ~a_i~ (có thể mang giá trị âm do chứa phản vật chất).

Để kích hoạt một phản ứng nhiệt hạch tối đa, hệ thống yêu cầu chọn ra chính xác 3 lõi năng lượng khác nhau. Năng lượng sinh ra từ phản ứng sẽ bằng tích mức năng lượng của 3 lõi được chọn.

Trong quá trình kiểm tra định kỳ, hệ thống đưa ra ~q~ truy vấn. Mỗi truy vấn cung cấp một đoạn giới hạn từ chỉ số ~L~ đến ~R~. Nhiệm vụ của bạn là chọn ra 3 chỉ số ~i, j, k~ thỏa mãn ~L \le i < j < k \le R~ sao cho tổng năng lượng sinh ra ~a_i \cdot a_j \cdot a_k~ là lớn nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ (~3 \le n \le 2 \cdot 10^5~; ~1 \le q \le 5 \cdot 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~|a_i| \le 10^6~).
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~L~ và ~R~ (~1 \le L \le R - 2 < R \le n~), đại diện cho một truy vấn.

Output

~q~ dòng, mỗi dòng là mức năng lượng lớn nhất có thể đạt được ứng với từng truy vấn.

Sample Input

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

Sample Output

60
72

Bạn được cho một dãy số có ~n~ phần tử. Mỗi giá trị xuất hiện tối đa ~2~ lần.

Bạn muốn xóa tất cả phần tử trong dãy số này, và bạn được thực hiện hai thao tác sau:

• Xóa hai phần tử kề nhau nếu hai phần tử đó bằng nhau. Sau khi xóa, dãy được dồn lại.
• Đổi chỗ hai phần tử kề nhau.

Hãy in ra số thao tác tối thiểu cần để xóa tất cả các phần tử của dãy số này.

Input

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 10^5~) - số lượng bộ test.

Dòng đầu tiên của mỗi test gồm một số nguyên dương ~n~ (~1 \le n \le 363636~) - số phần tử của dãy.

Dòng thứ hai của mỗi test gồm ~n~ số nguyên dương ~a_i~ (~1 \le a_i \le 10^9~) mô tả các phần tử của dãy.

Dữ liệu đảm bảo tổng của ~n~ qua mọi test không vượt quá ~676767~.

Output

Với mỗi test, in ra số thao tác tối thiểu cần thiết. Nếu không thể xóa hết dãy, in ra ~-1~.

Sample Input

2
6
1 1 2 2 3 3
6
1 9 9 8 1 8

Sample Output

3
4

Đây là bài toán tương tác.

Nhắc tới 12 năm học trò, có lẽ đó là quãng thời gian thanh xuân rực rỡ và thuần khiết nhất mà bất kỳ ai đã đi qua đều mang theo một niềm khắc khoải mong nhớ. Đó là những buổi sáng vội vã đạp xe dưới vòm cây rợp bóng, là tiếng trống trường vang vọng xé toạc không gian tĩnh lặng, và là những rung động ngây ngô giấu kín dưới ngăn bàn. Những năm tháng ấy trôi qua nhanh như một cái chớp mắt, nhường chỗ cho những bộn bề lo toan của tuổi trưởng thành, nhưng lại để lại trong hành trang bước vào đời của mỗi người là vô vàn những kỷ niệm đẹp đẽ, trong trẻo không thể nào bôi xóa.

Và trong chiếc hộp lưu giữ những ký ức vô giá ngày ấy, có lẽ, trò chơi cờ caro vẫn luôn nằm gọn gàng, vẹn nguyên ở một góc nhỏ thân thương nhất. Không cần đến những thiết bị điện tử đắt tiền hay mạng internet siêu tốc, một "trận chiến" nảy lửa có thể dễ dàng được triển khai chỉ bằng một trang giấy nháp xé vội và hai chiếc bút bi. Những đường kẻ ngang dọc vụng về dần được lấp đầy bởi những dấu X và O, mang theo cả sự tập trung cao độ, những tiếng cười khúc khích nén chặt, và đôi khi là cả cái giật mình thon thót khi bất chợt bắt gặp ánh mắt nghiêm khắc của thầy cô đang nhìn xuống từ bục giảng.

Trò chơi giản dị ấy không chỉ là phương thức hoàn hảo để những cô cậu học trò xua đi cơn buồn ngủ trong các tiết học dài lê thê, mà còn là sợi dây vô hình gắn kết những tình bạn tuổi hồng. Mỗi ván cờ khép lại, tờ giấy nháp chằng chịt vết mực lại được vo tròn nhét vội vào hộc bàn, nhưng những khoảnh khắc "đấu trí" ngây ngô, những lần năn nỉ xin đi lại một nước hay tiếng reo hò đắc thắng sẽ còn in hằn mãi theo năm tháng. Để rồi nhiều năm sau, giữa bộn bề cuộc sống, khi vô tình nhìn thấy một tờ giấy kẻ ô li, ta lại bất giác mỉm cười, nhớ về một thời ta đã từng có một "đối thủ" ngồi cùng bàn tuyệt vời đến thế.

Trong bài toán này, chúng ta xét một trò chơi cờ caro đơn giản với bảng kích thước ~3636 \times 3636~, với các hàng và cột được đánh số từ ~1~. Bạn sẽ chơi với máy chấm, và bạn được quyền chọn đi trước hay đi sau. Bạn sẽ thắng nếu tạo được một hàng ngang, một cột dọc, hay một đường chéo với độ dài ~3~.

Bạn chỉ được đi tối đa ~100~ nước, nếu vượt quá con số này, bạn sẽ thua cuộc.

Tương tác

Đầu tiên, chương trình của bạn cần in ra first hoặc second tương ứng bạn muốn đi trước hay đi sau.

Sau đó, trò chơi bắt đầu. Các lượt đi sẽ diễn ra luân phiên:

• Đến lượt bạn: Bạn cần in ra hai số nguyên dương ~x, y~ (~1 \le x, y \le 3636~) tương ứng ô bạn muốn đi. Ô này phải chưa từng được đi trước đó.
• Đến lượt máy chấm: Máy chấm sẽ in ra hai số nguyên dương ~x, y~ tương tự như trên, hoặc hai số ~-1~ nếu máy chấm nhận thua. Nếu máy chấm nhận thua, bạn cần kết thúc chương trình để nhận Kết quả đúng.

Nếu bạn nhận thua, bạn cần in ra hai số ~-1~ và kết thúc chương trình.

Sau mỗi lần in dữ liệu, bạn cần flush dữ liệu để đảm bảo tương tác với máy chấm thành công.

Sample

Cho mảng ~a~ gồm ~n~ phần tử, thực hiện ~q~ truy vấn gồm một trong các loại sau:

• ~1~ ~x~: Tăng tất cả phần tử trong mảng lên ~x~ đơn vị.
• ~2~ ~x~: Giảm tất cả phần tử trong mảng đi ~x~ đơn vị.
• ~3~ ~x~: Thêm phần tử ~x~ vào đầu dãy. Sau thao tác này, ~n~ tăng lên ~1~.
• ~4~ ~x~: Thêm phần tử ~x~ vào cuối dãy. Sau thao tác này, ~n~ tăng lên ~1~.
• ~5~: Sắp xếp dãy theo thứ tự tăng dần.
• ~6~: Sắp xếp dãy theo thứ tự giảm dần.
• ~7~: In ra phần tử đầu tiên của dãy, sau đó bỏ phần tử đó đi. Dữ liệu đảm bảo dãy có ít nhất ~1~ phần tử.
• ~8~: In ra phần tử cuối cùng của dãy, sau đó bỏ phần tử đó đi. Dữ liệu đảm bảo dãy có ít nhất ~1~ phần tử.

Yêu cầu: Với mỗi truy vấn loại ~7~ và ~8~, in ra kết quả tương ứng.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ và ~q~ (~1 \le n, q \le 2 \times 10^5~) - số phần tử trong mảng và số truy vấn.

Dòng thứ hai gồm ~n~ số nguyên ~a_i~ (~0 \le |a_i| \le 10^9~) thể hiện mảng.

~q~ dòng tiếp theo, mỗi dòng thể hiện một truy vấn. Tất cả ~x~ trong mọi truy vấn sẽ có giá trị tuyệt đối không quá ~10^9~.

Output

Với mỗi truy vấn loại ~7~ hoặc ~8~, in ra đáp án trên một dòng.

Sample Input

5 4
4 5 6 7 8
8
6
3 3
7

Sample Output

8
3

Mảng ban đầu là ~4, 5, 6, 7, 8~.

Sau truy vấn ~1~, mảng là ~4, 5, 6, 7~.

Sau truy vấn ~2~, mảng là ~7, 6, 5, 4~.

Sau truy vấn ~3~, mảng là ~3, 7, 6, 5, 4~.

Sau truy vấn ~4~, mảng là ~7, 6, 5, 4~.

Đây là phiên bản dễ của bài toán. Khác biệt duy nhất là trong phiên bản này, ~k=1~.

Bạn được cho một xâu nhị phân ~s~ độ dài ~n~. Một đoạn con ~s_l s_{l+1}\dots s_r\ (1\le l\le r\le n)~ được gọi là "đẹp" nếu số ký tự 0 và số ký tự 1 xuất hiện trong đoạn con đó bằng nhau.

Độ đẹp của một xâu nhị phân bằng số đoạn con "đẹp" xuất hiện trong xâu đó.

Bạn được phép thực hiện thao tác sau tối đa ~k~ lần:

• Đổi chỗ hai ký tự kề nhau (~s_i~ và ~s_{i + 1}~).

Nhiệm vụ của bạn là xác định độ đẹp tối đa của xâu có thể đạt được sau khi thực hiện thao tác.

Input

Mỗi bộ test bao gồm nhiều trường hợp thử nghiệm. Dòng đầu tiên gồm số nguyên dương ~t~ là số trường hợp thử nghiệm ~(1\le t\le 10^4)~. Định dạng với mỗi trường hợp thử nghiệm được mô tả như sau:

Dòng đầu tiên trong mỗi trường hợp thử nghiệm gồm hai số nguyên dương ~n~ và ~k\ (1\le n\le 2\times 10^5,k=1)~ - độ dài xâu nhị phân ~s~ và số thao tác tối đa.

Dòng thứ hai trong mỗi trường hợp thử nghiệm gồm một xâu nhị phân ~s~ độ dài ~n~. Dữ liệu đảm bảo ~s~ chỉ bao gồm các ký tự 0 và 1.

Dữ liệu đảm bảo tổng ~n~ trong tất cả trường hợp thử nghiệm không vượt quá ~2\times 10^5~.

Output

Với mỗi trường hợp thử nghiệm, in ra một số nguyên không âm trên một dòng tương ứng với độ đẹp tối đa của xâu ~s~ có thể đạt được.

Sample Input

2
4 1
0110
4 1
0101

Sample Output

4
4

Trong test 1: Chọn ~i=1~ để hoán đổi ~s_1~ và ~s_2~, xâu trở thành 1010. Lúc này số lượng đoạn con đẹp là 4: ~10~, ~01~, ~10~, và ~1010~. Đây là kết quả tối ưu.

Đây là phiên bản khó của bài toán. Khác biệt duy nhất là trong phiên bản này, ~k=2~.

Bạn được cho một xâu nhị phân ~s~ độ dài ~n~. Một đoạn con ~s_l s_{l+1}\dots s_r\ (1\le l\le r\le n)~ được gọi là "đẹp" nếu số ký tự 0 và số ký tự 1 xuất hiện trong đoạn con đó bằng nhau.

Độ đẹp của một xâu nhị phân bằng số đoạn con "đẹp" xuất hiện trong xâu đó.

Bạn được phép thực hiện thao tác sau tối đa ~k~ lần:

• Đổi chỗ hai ký tự kề nhau (~s_i~ và ~s_{i + 1}~).

Nhiệm vụ của bạn là xác định độ đẹp tối đa của xâu có thể đạt được sau khi thực hiện thao tác.

Input

Mỗi bộ test bao gồm nhiều trường hợp thử nghiệm. Dòng đầu tiên gồm số nguyên dương ~t~ là số trường hợp thử nghiệm ~(1\le t\le 10^4)~. Định dạng với mỗi trường hợp thử nghiệm được mô tả như sau:

Dòng đầu tiên trong mỗi trường hợp thử nghiệm gồm hai số nguyên dương ~n~ và ~k\ (1\le n\le 2\times 10^5,k=2)~ - độ dài xâu nhị phân ~s~ và số thao tác tối đa.

Dòng thứ hai trong mỗi trường hợp thử nghiệm gồm một xâu nhị phân ~s~ độ dài ~n~. Dữ liệu đảm bảo ~s~ chỉ bao gồm các ký tự 0 và 1.

Dữ liệu đảm bảo tổng ~n~ trong tất cả trường hợp thử nghiệm không vượt quá ~2\times 10^5~.

Output

Với mỗi trường hợp thử nghiệm, in ra một số nguyên không âm trên một dòng tương ứng với độ đẹp tối đa của xâu ~s~ có thể đạt được.

Sample Input

2
6 2
001011
5 2
00101

Sample Output

9
6

Trong test 1, ta hoán đổi ~s_2~ và ~s_3~, sau đó hoán đổi ~s_4~ và ~s_5~, ta được xâu 010101 có độ đẹp bằng ~9~.

Cho một cây gồm ~n~ đỉnh và ~n - 1~ cạnh.

Hãy đếm số cặp ~(x, y)~ (~1 \le x < y \le n~), mà khi ta thêm một cạnh ~(x, y)~ vào cây, thì kích thước tập độc lập cực đại trên đồ thị mới là không đổi.

Một tập độc lập cực đại trên đồ thị là một tập nhiều đỉnh nhất, sao cho không có hai đỉnh nào có cạnh nối trực tiếp.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 3 \times 10^5~) là số đỉnh của cây.

~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u, v~ (~1 \le u, v \le n~) mô tả một cạnh của cây.

Output

Số cặp đỉnh thỏa mãn đề bài.

Sample Input

5
1 2
2 3
3 4
3 5

Sample Output

9

Các cặp đỉnh thỏa mãn là ~(1, 2)~, ~(2, 3)~, ~(3, 4)~, ~(3, 5)~, ~(1, 3)~, ~(1, 4)~, ~(1, 5)~, ~(2, 4)~, ~(2, 5)~.

Trong giới học sinh chuyên, kỳ thi Học sinh giỏi Quốc gia luôn được ví như một cuộc rèn luyện khổ hạnh. Để chạm tay vào những tấm huy chương danh giá, các tuyển thủ phải đánh đổi hàng tháng trời vùi đầu vào phòng đội tuyển. Dù không có bất kỳ một văn bản chính thức nào quy định, nhưng giữa các thầy cô giáo bộ môn và ban giám hiệu luôn tồn tại một "luật ngầm" đầy tinh tế: tạo mọi điều kiện tối đa cho các sĩ tử trong học kỳ đó. Những bài kiểm tra 15 phút, những buổi dò bài đầu giờ hay cả những cột điểm giữa kỳ đều được nhẹ nhàng gác lại hoặc châm chước, nhường trọn quỹ thời gian cho những chuyên đề chuyên sâu và những đêm thức trắng cùng đam mê.

Thế nhưng, ánh hào quang nào rồi cũng đến lúc nhường chỗ cho thực tại. Khi kỳ thi khép lại, cũng là lúc những "chiến thần" đội tuyển phải tháo bảng tên thí sinh để trở về với nhịp sống của một học sinh chính khóa bình thường. Lúc này, họ phải đối mặt với một món nợ khổng lồ: học lại toàn bộ chương trình của các môn học đã bị bỏ lỡ từ lâu. Từ những chuỗi phản ứng Hóa học rắc rối, những mốc sự kiện Lịch sử dài đằng đẵng, cho đến những bài phân tích Văn học phức tạp... tất cả bỗng chốc trở thành một mớ dây leo chờ được gỡ rối.

Nhìn từ bên ngoài, việc phải lấp đầy lỗ hổng kiến thức khổng lồ ấy trong thời gian ngắn nghe chừng là một thử thách vô vọng. Các tuyển thủ thường bị trêu đùa và gắn mác là những kẻ "học lệch", chỉ biết mỗi môn chuyên mà mù tịt những môn còn lại. Nhưng thực tế chứng minh điều ngược lại, với nền tảng tư duy logic sắc bén đã được tôi luyện qua những thử thách hóc búa nhất, việc "lấy lại gốc" đối với họ không hề gian nan như người ta tưởng. Phần vì khả năng tiếp thu và tự học của họ đã đạt đến độ chín, phần vì mục tiêu ban đầu thường rất thực dụng và khiêm tốn: chỉ cần điểm số vừa đủ an toàn, qua mức trung bình là thành công.

Tuy nhiên, mọi thứ sẽ trở thành một câu chuyện hoàn toàn khác nếu những học sinh "học lệch, mất gốc" ấy thực sự bật chế độ nghiêm túc. Một khi họ quyết tâm dồn sự tập trung và khả năng phân tích hệ thống của mình vào các môn học trên lớp, sức bật của họ là không thể cản phá. Những bài tập từng bị coi là rắc rối bỗng chốc được giải quyết bằng một tư duy rành mạch, tối ưu và đi thẳng vào bản chất vấn đề. Lúc bấy giờ, họ không chỉ lấp đầy khoảng trống kiến thức trong nháy mắt, mà đôi khi còn bứt phá mạnh mẽ, vượt mặt cả những học sinh chăm chỉ nhất lớp, khẳng định một chân lý: tư duy nhạy bén chính là vũ khí tối thượng để chinh phục mọi rào cản.

Trong quá trình lấy gốc đầy quyết tâm ấy, cậu học sinh nhận thấy có ~n~ chuyên đề cần phải chinh phục. Mỗi chuyên đề thứ ~i~ mang lại hai loại lợi ích: hiệu quả cố định ~a_i~ và hiệu quả không cố định ~b_i~.

Việc rèn luyện chuyên đề thứ ~i~, trong giây đầu tiên, sẽ giúp cậu bứt phá và tăng sức mạnh lên một lượng đúng bằng ~a_i + b_i~. Sau đó, cứ mỗi giây tiếp theo dành cho chuyên đề này, phần sức mạnh tăng thêm sẽ bị suy giảm đi ~1~ đơn vị do sự bão hòa kiến thức, cho tới khi chạm đáy và chỉ duy trì ở mức hiệu quả cố định.

Ví dụ, một chuyên đề có hiệu quả cố định là ~6~ và hiệu quả không cố định là ~2~, nếu học sinh đó học chuyên đề này trong ~4~ giây, sức mạnh của học sinh đó sẽ tăng thêm ~(6 + 2) + (6 + 1) + (6 + 0) + (6 + 0) = 27~ đơn vị.

Học sinh ấy chỉ có quỹ thời gian vỏn vẹn ~t~ giây để học. Hãy tính sức mạnh lớn nhất mà cậu có thể đạt được.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 2 \times 10^5~) là số chuyên đề.

Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^8~) - hiệu quả cố định của chuyên đề thứ ~i~.

Dòng tiếp theo chứa ~n~ số nguyên dương ~b_1, b_2, ..., b_n~ (~1 \le b_i \le 10^8~) - hiệu quả không cố định của chuyên đề thứ ~i~.

Dòng cuối cùng chứa số nguyên dương ~t~ (~1 \le t \le 10^{10}~) - thời gian học sinh ấy có.

Output

Sức mạnh lớn nhất học sinh đó có thể đạt được.

Sample Input

2
6 4
2 3
5

Sample Output

34

Trong bảng chữ cái tiếng Anh có ~5~ nguyên âm là a, e, i, o, u, còn lại là ~21~ phụ âm.

Xét một xâu ~s~ chỉ gồm các ký tự in thường. Xâu ~s~ được gọi là xâu đặc biệt nếu:

• Có ít nhất một nguyên âm.
• Có ít nhất một phụ âm.
• Các nguyên âm nằm về một phía (trái / phải) của xâu.

Ví dụ, xâu aaab, bhheui là xâu đặc biệt, còn các xâu aaa, aeiou, ababah không phải là xâu đặc biệt.

Cho xâu ~s~. Đếm số xâu con (không cần liên tiếp) của xâu ~s~ là xâu đặc biệt.

Input

Dòng đầu tiên gồm số nguyên dương ~T~ (~1 \le T \le 10^4)~ là số truy vấn.

Mỗi truy vấn gồm xâu ~s~ (~1 \le |s| \le 3 \times 10^5~).

Dữ liệu đảm bảo ~\sum |s| \le 3 \times 10^5~.

Output

~T~ dòng, mỗi dòng là số xâu con (không cần liên tiếp) của xâu ~s~ là xâu đặc biệt.

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 ~20032024~.

Sample Input

5
ab
aab
aba
aaa
code

Sample Output

1
3
2
0
6