Trong hành trình chinh phục những vì sao, kỵ sĩ Luna phải băng qua một cánh đồng có hình chữ nhật kích thước ~n \times m~. Kỵ sĩ cưỡi trên một con ngựa, xuất phát từ ô ~(1,1)~ ở góc dưới bên trái để đi đến trên điểm cuối của cánh đồng ở góc trên bên phải. Con ngựa này có thể nhảy những bước giống như mã trên bàn cờ vua, tức là từ ô ~(a,b)~ có thể nhảy đến ô ~(c,d)~ mà ~|(a-c)(b-d)|=2.~ Hãy giúp kỵ sĩ đếm xem có bao nhiêu cách để băng qua cánh đồng này nhé, biết rằng con ngựa chỉ nhảy sang phải và hướng lên trên, không bao giờ đi lùi bước.

Input: một dòng duy nhất gồm hai số nguyên dương ~n,m~ trong đó ~1 \le n, m \le 10^6.~

Output: đáp số của bài toán, chia dư cho ~10^9+7.~

Sample input 1:

4 4

Sample output 1:

2

Sample input 2:

2023 2023

Sample output 2:

320887707

Để chuẩn bị cho lễ phát động kỳ thi Olympic Tin học 2023, ba bạn trong team Lina, Anna và Luna đã ngồi trang trí băng rôn bằng cách viết liên tiếp các ký tự ~O, L, P~ thành một dãy dài. Nhưng vì băng rôn hơi dài nên thầy lãnh đội Tina muốn cắt ra một đoạn nhỏ sao cho trong đoạn đó có một ký tự nào đó xuất hiện từ ~3~ lần trở lên. Bạn hãy giúp team đếm thử xem có bao nhiêu cách cắt như vậy nhé?

Input: một dòng duy nhất là chuỗi chứa các ký tự ~O, L, P~, mỗi ký tự có thể xuất hiện ~0~ hoặc nhiều lần. Độ dài chuỗi không vượt quá ~10^5.~

Output: đáp số của bài toán.

Sample input 1:

OLPOLP

Sample output 1:

0

Sample input 2:

OOOOO

Sample output 2:

6

Giải thích: trong VD1, ta thấy không có ký tự nào xuất hiện 3 lần trở lên nên đáp số là 0, còn trong VD2, ta có các cách chọn chuỗi con từ các cặp vị trí sau: ~(1,3),(1,4),(1,5),(2,4),(2,5),(3,5).~

Trong giờ học Toán, hai bạn Kina và Luna đang ngồi chơi caro thì bị thầy Tina bắt gặp. Thấy hai bạn đang vẽ sẵn một bảng vuông ~n \times n~ nên thầy bèn ra luôn một đề bài như sau: cho hai số nguyên dương ~a, m~ trong đó ~a~ chia hết cho ~m~, hỏi có bao nhiêu cách điền các số nguyên từ ~1 \to a~ vào bảng, mỗi số một ô sao cho tổng các số trên mỗi hàng và mỗi cột đều chia hết cho ~m~?

Hai bạn đã tính ra kết quả nhưng vì giá trị quá lớn nên đã xin phép thầy Tina là lấy mod ~19741991~ (là năm sinh của hai bạn ghép lại), bây giờ mọi người thử cùng trải nghiệm bài toán vui này nhé.

Thầy Tina sau khi thấy hai bạn giải khá lâu mà chưa ra nên đã có chút gợi ý: "hãy chú ý vào hình vuông con ~(n-1) \times (n-1)~ ở góc trên bên trái."

Input: một dòng duy nhất gồm ba số nguyên dương ~n, m, a~ với ~2 \le n, m, a \le 10^9~, cho biết rằng ~a~ chia hết cho ~m~.

Output: đáp số của bài toán, lấy modulo ~19741991.~

Sample input 1:

2 2 2

Sample output 1:

2

Sample input 2:

2023 5 15

Sample output 2:

6854631

Giải thích:

Ở ví dụ 1, ta liệt kê được hai bảng full số 1 và full số 2.

Sau một thời gian con tàu đã phóng để thăm dò các tiểu hành tinh đã trả về n bản báo cáo chụp được được ở các tiểu hành tinh. Trong bản báo cáo thứ ~i~ sẽ có thông tin vị trí (~x_i, y_i, z_i~) của hành tinh và ~v_i~ sinh vật ở trên hành tinh đó. Và trong những báo cáo về cùng một hành tinh, ta sẽ luôn lấy kết quả lớn nhất vì báo cáo có nhiều sinh vật nhất sẽ bao quát số lượng sinh vật ở các báo cáo còn lại.

Từ thông tin trên cần bạn tìm ra ~3~ hành tinh có khả năng có nhiều sinh vật nhất để tìm hiểu về hệ sinh tái ở đó và ~3~ hành tinh có ít sinh vật nhất để bảo tồn.

Input:

• Dòng đầu tiên chứa số nguyên dương ~n~ (~3 \le n \le 10^5~)
• ~N~ dòng tiếp theo chứa ~4~ số nguyên dương lần lượt là ~x_i, y_i, z_i, v_i~ (~x_i, y_i, z_i, v_i \le 10^9~)

Luôn đảm bảo sẽ có ít nhất ~3~ tiểu hành tinh.

Output:

• ~3~ dòng đầu tiên chứa lần lượt ~x_i, y_i, z_i, v_i~ là tọa độ và số lượng sinh vật trên các hành tinh có số sinh vật lớn nhất. Được xếp theo thứ tự từ lớn về nhỏ.
• ~3~ dòng tiếp theo chứa lần lượt ~x_i, y_i, z_i, v_i~ là tọa độ và số lượng sinh vật trên các hành tinh có số sinh vật lớn nhất. Được xếp theo thứ tự từ nhỏ đến lớn.

Nếu có nhiều hành tinh cùng số lượng sinh vật mà có thể đề cử vào danh sách này, ta sẽ ưu tiên các hành tinh có chỉ số lớn nhất đến nhỏ nhất theo thứ tự lần lượt các trục là ~z, x, y~. Ví dụ:

• Nếu có ~3~ hành tinh cùng số lương sinh vật mà có tọa độ là (~1,2,3~), (~3,2,1~), (~2,1,3~)
• Thì thứ tự tư tiên sẽ là (~2,1,3~) ~>~ (~1,2,3~) ~>~ (~3,2,1~)

Sample input:

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

Sample output:

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

Trong một buổi tiệc tại CLB H3.2 phiên bản mở rộng của Luna, có tất cả ~n~ thành viên, và mỗi người có thể nói một hoặc vài ngôn ngữ. Biết rằng hai người nói cùng ngôn ngữ thì có thể giao tiếp với nhau và có đúng ~n-1~ cặp như thế. Ngoài ra, những cặp còn lại thì đều có thể giao tiếp với nhau nhờ một hoặc vài người khác phối hợp phiên dịch giúp. Tuy nhiên, các cặp giao tiếp mà cần từ ~2~ người phiên dịch trở lên thì cảm thấy không thoải mái lắm. Vì vậy, họ đề xuất với BTC sẽ sử dụng "Google translate" để giao tiếp cho thuận lợi. Bạn hãy giúp Luna đếm xem có bao nhiêu cặp cần sử dụng công cụ trợ giúp nhé.

Input:

Dòng đầu tiên gồm số nguyên dương ~n~ với ~2 \le n \le 70000.~ Trong ~n~ dòng tiếp theo, mỗi dòng là một cặp số ~x, y~ cho biết số thứ tự của những người có thể giao tiếp với nhau. Các cặp số này đều phân biệt và đảm bảo điều kiện đề bài.

Output:

Số cặp cần sử dụng Google translate.

Sample input 1:

4

1 2

1 3

1 4

Sample output 1:

0

Sample input 2:

4

1 2

2 3

3 4

Sample output 2:

1

Giải thích:

Trong VD1, do tất cả những người trong buổi tiệc đều có thể giao tiếp trực tiếp với nhau hoặc thông qua trung gian là người ~1~ nên tất cả đều cảm thấy thoải mái, không ai cần công cụ hỗ trợ. Còn trong VD2, ta thấy có cặp ~(1,4)~ cần đến hai người phiên dịch trung gian là ~2,3~ nên họ cảm thấy không thoải mái.

Trong quá trình tranh giành chức vụ Cố vấn cao cấp của CLB H3.2, hai coder Đức Tài và Trần Lộc đã biểu diễn nhiều kỹ năng coding đỉnh cao của mình cho thầy Luna xem. Do qua nhiều vòng nhưng chưa phân thắng bại, trong vòng cuối, thầy Luna muốn dựa theo số phận để lựa chọn. Biết rằng Tài sinh vào tháng 9, còn Lộc sinh vào tháng 11 nên thầy cho một số ~n~ và bỏ đi một vị trí bất kỳ trong đó, thầy yêu cầu hai bạn chọn một số để điền vào vị trí kia sao cho số thu được chia hết cho tháng sinh của mình (cho phép số ~0~ đứng đầu). Ai thu được số lớn hơn (hoặc người kia không điền được số vào) thì thắng cuộc (tất nhiên ai cũng muốn điền số càng lớn càng tốt), còn nếu không phân thắng bại thì sẽ cho em Thiên Ban acc xanh dương CF làm chức vụ này.

Input: Một dòng duy nhất gồm một số ~n~ có giá trị không vượt quá ~10^{100000}~, trong đó có một vị trí được điền bởi dấu ?

Output:

Tên của Cố vấn cao cấp được chọn: Ban, Tai hoặc Loc.

Sample input:

202?

Sample output:

Tai

Giải thích: ta thấy Tài có thể điền số 5 vào để được 2025 chia hết cho 9, còn Lộc chỉ có thể điền số 4 vào để được 2024 chia hết cho 11. Vì số của Tài lớn hơn nên chức vụ sẽ thuộc về Tài.

Trong CLB lập trình H3.2, có ~n~ thành viên với leader Trung Phan có STT ~1~, còn các thành viên kia sẽ có STT từ ~2,3,...,n~. Dưới leader này sẽ có một số thư ký, rồi dưới mỗi thư ký sẽ có một số trợ lý thư ký, ..., nói chung quan hệ cấp bậc trong CLB phân biệt khá rõ, tạo thành một mô hình cây. Các thành viên mới vào sẽ thuộc 'tầng lớp' thấp nhất (có thể gọi là cộng tác viên). Thầy Luna thường giao các task cho một thành viên nào đó của CLB, và nếu hoàn thành tốt thì được thưởng, còn không thì sẽ bị phạt với một mức tiền nhất định. Có một điều đặc biệt, một khi thành viên được ~x~ đồng (số này có thể âm hoặc dương, tùy vào bị phạt hay được thưởng) thì tất cả cấp dưới của người này sẽ được ~-x~ đồng, rồi cấp dưới nữa lại được ~-(-x)=x~ đồng, và cứ thế lan truyền xuống cấp thấp nhất. Ban đầu mỗi người sẽ có 0 đồng. Thầy Luna thắc mắc tại một thời điểm nào đó, một người có STT ~i~ sẽ đang có bao nhiêu tiền?

Input:

Dòng đầu tiên gồm hai số nguyên dương ~n, m~ với ~2 \le n, m \le 10^5.~

Mỗi dòng trong ~n-1~ dòng tiếp theo sẽ gồm một cặp số ~x,y~ cho biết STT của hai thành viên có làm việc trực tiếp với nhau (chưa biết ai là cấp trên của ai), chỉ biết STT ~1~ là cấp cao nhất.

Mỗi dòng trong ~m~ dòng tiếp theo sẽ có một trong hai dạng (cho biết sẽ có ít nhất một câu hỏi dạng 2):

1 ~i~ ~x~: người thứ ~i~ sẽ nhận một giá trị là ~x~, trong đó ~x \le 2023.~

2 ~i~: yêu cầu cho biết số tiền hiện tại mà người thứ ~i~ trong CLB có.

Output:

Trả lời cho các câu hỏi dạng 2, theo thứ tự từ trên xuống.

Sample input:

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

Sample output:

0
3

Alibaba trong truyền thuyết ngàn lẻ một đêm thì có ~40~ tên cướp, nhưng Ali Vũ của H3.2 thì chỉ có ~20~ viên kẹo thôi. Mỗi viên kẹo của Vũ có một khối lượng nguyên dương nhất định. Vũ giao cho thư ký Ban và Mạnh sắp xếp các viên kẹo này thành hai hàng, mỗi hàng ~10~ viên. Để gây ấn tượng với sếp, Ban đã xếp ~10~ kẹo nặng nhất thành một hàng, còn Mạnh xếp ~10~ viên kẹo nhẹ nhất thành một hàng khác sao cho chênh lệch hai viên kề nhau trên từng hàng là một số nguyên tố. Hỏi hai bạn có làm được điều này không?

Input:

Một dòng duy nhất gồm ~20~ số nguyên dương không vượt quá ~10^6~ và không nhất thiết phân biệt.

Output:

Nếu không ai xếp được thì in ra OH NO, nếu có đúng một người xếp được thì in ra OKELA, còn cả hai cùng xếp được thì in ra OH YEAH.

Sample input:

2 2 2 2 2 4 4 4 4 4 5 5 5 5 5 8 8 8 8 8

Sample output:

OH YEAH

Giải thích: các bạn có thể xếp như sau:

Mạnh: 2 4 2 4 2 4 2 4 2 4 -> chênh lệch giữa hai viên kẹo liên tiếp đều là 2, là số nguyên tố.

Ban: 5 8 5 8 5 8 5 8 5 8 -> chênh lệch giữa hai viên kẹo liên tiếp đều là 3, là số nguyên tố.

Mẹ mới mua ~n~ viên kẹo về cho ba anh em, người anh cả được phân công chia kẹo hết số kẹo đó mà làm sao cho mỗi người đều có số lượng kẹo là số chẵn và không ai là không có kẹo.

Hỏi liệu anh cả có thể chia được không?

Input:

• Dòng đầu tiên chứa số nguyên ~n~ là số kẹo mẹ mua. (~ 0 \leq n \leq 100~)

Output:

• Một dòng duy nhất chứa chuỗi "YES" nếu anh cả có thể chia được, còn nếu không cách nào chia được thì ra "NO".

Sample input:

8

Sample output:

YES

Một ngày nọ, có hai vị khách là Aquarius và Melyrius đến thăm CLB H3.2. Thầy Luna chiêu đãi họ bằng hai thùng kẹo mà mỗi thùng đều có ~n~ túi kẹo, mỗi túi kẹo chứa số lượng không quá ~10^5~ viên. Vì rất ga lăng nên Aquarius muốn rằng mọi túi kẹo của mình đều có số kẹo không vượt quá mọi túi kẹo của Melyrius. Để làm được điều này, Aquarius sẽ thực hiện các thao tác sau: chọn một túi kẹo của mình và ăn bớt ~1~ viên trong đó, hoặc chọn một túi kẹo của Melyrius và xin thầy Luna thêm ~1~ viên để thêm vào đó. Hỏi Aquarius cần làm điều này ít nhất bao nhiêu lần để đạt được mục tiêu ga lăng của mình?

Input:

Dòng đầu tiên gồm số nguyên dương ~n~ với ~1 \le n \le 10^5.~ Trong hai dòng tiếp theo, mỗi dòng sẽ gồm ~n~ số nguyên dương không vượt quá ~10^5~ (dòng thứ hai ứng với kẹo của Melyrius, còn dòng thứ ba ứng với kẹo của Aquarius).

Output:

Một số nguyên dương duy nhất cho biết số lần ít nhất cần thực hiện.

Sample input 1:

2
2 3
1 4

Sample output 1:

2

Sample input 2:

2
4 3
3 1

Sample output 2:

0

Giải thích: trong VD 1, Aquarius sẽ ăn của mình ~2~ viên trong túi thứ hai để còn ~(1,2)~; còn trong VD 2 thì điều kiện đã được thỏa mãn nên không cần thay đổi gì.

Cho tọa độ ~5~ điểm (~x_i, y_i~) trên hệ tọa độ Descartes và bán kính ~r~.

Nhờ bạn hãy kiếm tra xem tồn tại đường tròn bán kính ~r~ mà ~5~ điểm đã cho sẽ nằm trong hoặc nằm trên đường tròn đó.

Input:

• Dòng đầu tiên chứa số nguyên dương ~r~ là bán kính của đường tròn. (~ r \leq 100~)
• ~5~ dòng tiếp theo chứa ~2~ số nguyên ~x_i, y_i~ để mô tả tọa độ của điểm thứ ~i~. (~ x_i, y_i \leq 100~)

Output:

Một dòng duy nhất chứa chuỗi "YES" nếu tồn tại hình tròn đó còn ngược lại thì "NO".

Sample input 1:

1
0 0
0 1
1 0
0 -1
-1 0

Sample output 1:

YES

Sample input 2:

1
1 1
0 1
1 0
0 -1
-1 0

Sample output 2:

NO

Hiện tại cuộc thi "Hành trình chinh phục những vì sao" đã đến kỳ thứ 2, nhưng vì sợ các thí sinh còn bỡ ngỡ với cách tính tiền thưởng mới, nên BTC quyết định sẽ để các bạn tự tay tính tiền thưởng đển hiểu hơn về nó.

Dưới đây là chi tiết cách tính thưởng của cuộc thi:

• Cuộc thi sẽ gồm n đội thi, cùng nhau giải k vấn đề trong h tiếng.
• Mỗi vấn đề sẽ có cố định 200.000 tiền thưởng và chỉ chia cho các team giải được vấn đề đó.
• Với mỗi vấn đề nếu đội thứ i giải đúng sẽ được ~p_i = (totalTime)/(t_i + 20*x_i)~ điểm. Trong đó:
  • ~t_i~: thời điểm đầu tiên làm đúng vấn đề đó của đội i.
  • ~x_i~: số lần làm sai vấn đề đó của đội i trước thời gian ~t_i~.
  • ~totalTime = h * 60~: tổng số phút diễn ra cuộc thi.
• Sau cùng, với mỗi vấn đề, đội i sẽ nhận số tiền thưởng theo tỉ lệ là: ~ rate_i = p_i/\sum{p_i} ~.
• Tổng số tiền thưởng của mỗi đội nhận được sẽ chỉ lấy phần nguyên để để dễ dàng quyết toán.

Từ cách tính thưởng trên, ta có thể hoàn toàn rút ra những kết luận:

• Tỉ lệ của điểm càng cao thì tiền thưởng càng nhiều.
• Điểm càng cao thì sẽ càng nhiều tiền thưởng.
• Làm đúng càng sớm thì điểm nhận được càng cao.
• Làm sai càng nhiều sẽ càng ít điểm.
• Làm sai càng sớm thì tiền thưởng càng lỗ.
• Vấn đề càng ít đội thi giải đúng thì tiền thưởng càng nhiều.

Dựa trên mô tả trên, hãy tính ra chính xác tổng số tiền thưởng của mỗi đội thi nhận được sau cùng dựa trên danh sách trạng thái nộp bài mà hệ thống ghi nhận khi cuộc thi kết thúc.

Input:

• Dòng đầu tiên chứa ~4~ số nguyên dương lần lượt là ~n, k, h, q~ có ý nghĩa lần lượt là số lượng đội thi, số lượng vấn đề, tổng số giờ của cuộc thi và số trạng thái trong toàn bộ cuộc thi. (~n, k, h \leq 10, q \leq 1000~)
• ~q~ dòng tiếp theo chứa ~4~ thành phần liên tiếp lần lượt là: ~t, p, ts, s~ để mô tả ~1~ trạng thái nộp bài giải được ghi nhận trong hệ thống.
• Trong đó:
  • ~t~ : số thứ tự của đội thi. (~ 1 \leq t \leq n~)
  • ~p~ : số thứ tự của vấn đề mà đội thi ~t~ nộp bài giải. (~ 1 \leq p \leq k~)
  • ~ts~: thời điểm (tính theo phút) mà đội ~t~ nộp bài giải. (~0 \leq ts \leq totalTime~)
  • ~s~ : kết quả sau khi chấm của bài giải. (~ s \in \set{W, A}~) với ~W~ - nghĩa là ~WRONG\ ANSWER~ (bài giải đã sai) và ~A~ - nghĩa là ~ACCEPTED~ (bài giải đã đúng)
• Đảm bảo mỗi đội sẽ không nộp quá một lời giải trong cùng một phút.

Output:

• ~N~ dòng mà mỗi dòng chứa một số nguyên dương là tổng số tiền thưởng của đội thứ ~i~ nhận được sau khi tham gia cuộc thi.

Sample input:

2 2 2 5
1 1 20 W
2 2 30 A
2 1 40 W
1 1 60 A
1 2 90 A

Sample output:

250
150

Trong giờ giải lao của môn Xử lý dữ liệu nhiễu, thầy Huna phát cho Luna một dãy số nguyên có độ dài ~n \ge 2~. Thầy yêu cầu bạn tính tích các số của dãy. Là một sinh viên giỏi của lớp, Luna có thể thực hiện dễ dàng bằng một dòng lệnh trong Python. Tuy nhiên, thầy Huna muốn bạn áp dụng kiến thức trong bài giảng về xử lý nhiễu, yêu cầu Luna phải tìm và xóa đi đúng một số nào đó để tích của các số còn lại là lớn nhất có thể. Bạn hãy cùng Luna giải bài toán này nhé, cho biết cần xóa số nào. Trong trường hợp có số nhiều cách xóa nhưng ra cùng một kết quả thì xóa đi số lớn nhất trong các cách (tham khảo thêm Ví dụ).

Input:

Dòng đầu tiên gồm số nguyên dương ~n~ với ~2 \le n \le 10^5.~ Dòng tiếp theo gồm ~n~ số, có thể có âm lẫn dương và số ~0~, các số không nhất thiết phân biệt và có giá trị tuyệt đối không vượt quá ~10^5.~

Output:

Giá trị của số cần xóa đi.

Sample input 1:

4

0 1 2 3

Sample output 1:

0

Sample input 2:

4

0 0 -1 2

Sample output 2:

2

Giải thích: trong VD1, ta thấy nếu xóa số ~0~ thì tích thu được sẽ dương nên số cần xóa là ~0~, không có lựa chọn nào khác. Còn ở VD2, ta thấy có hai số ~0~ nên việc xóa đi một số cũng không giải quyết được gì, tích các số còn lại luôn bằng ~0~. Vì thế ta có thể xóa bất kỳ số nào, và theo yêu cầu đề nên ta xóa ~2.~