Để chuẩn bị cho dịp nghỉ lễ, CLB H3.2 đã dùng ~n~ sticker để trang trí cho lab. Các bạn muốn dùng hết số sticker này và tạo thành hình chữ nhật có chu vi càng nhỏ càng tốt. Hãy giúp các bạn in ra hình chữ nhật đó nhé, mỗi sticker là một dấu ~\times~.

Input:

Một dòng duy nhất là số nguyên dương ~n~ với ~1 \le n \le 10^5.~

Output:

Bảng hình chữ nhật thỏa mãn điều kiện, nếu có hai hình có cùng chu vi (dạng ngang hoặc dọc) thì in nó theo dạng nằm ngang.

Sample input:

8

Sample output:

xxxx

xxxx

Giải thích: trong VD trên, ta thấy với 8 stickers, ta có thể tạo thành các hình chữ nhật kích thước ~8 \times 1, \, 1 \times 8, \, 2 \times 4, \, 4 \times 2~ với chu vi lần lượt là ~18, 18, 12, 12.~ Do đó, chu vi nhỏ nhất sẽ là ~12~, và để hình chữ nhật nằm ngang, ta sẽ in ra kích thước ~2 \times 4.~

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 một cuộc thi, có ~n~ thí sinh thuộc nhiều tỉnh thành, mỗi tỉnh thành sẽ được định danh bằng một mã số. Ban tổ chức hiện tại muốn thống kê danh sách các thí sinh theo tỉnh thành để hiểu hơn về danh sách thí sinh. Họ sẽ xếp khu vực có nhiều thí sinh nhất lên trước, ít hơn sẽ để ra sau. Nếu có hai khu vực cùng số lượng thí sính, thì sẽ để khu vực có mã số nhỏ hơn lên trước và lớn hơn để ở sau.

Dựa trên nguyên tắc đã nêu, nhờ bạn hãy tìm ra xem tỉnh thành nào có nhiều thí sinh thứ tư theo cách thống kê trên, nếu không có hãy xuất ra ~-1~.

Input:

• Dòng đầu tiên chứa số nguyên dương ~n~ là số lượng thí sinh. (~ n \leq 100~)
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_i~ là mã số tỉnh thành của thí sinh thứ ~i~. (~ a_i \leq 1000~)

Output:

• Một dòng duy nhất chứa mã số tỉnh thành đại diện cho khu vực xuất hiện nhiều thí sinh thứ tư trong cuộc thi.
• Nếu không có thì hãy xuất ra -1.

Sample input 1:

5
1 2 3 4 5

Sample output 1:

4

Sample input 2:

5
1 2 1 2 3

Sample output 2:

-1

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

Thầy Luna xếp các SV của CLB thành một hàng dọc để cho ba leader Trung, Nhân, Phú đi kiểm tra. Đi từ đầu dãy:

• Nếu tổng số nam hiện tại lớn hơn số nữ thì sẽ cho Trung ~1~ món quà;

• Nếu tổng số nữ hiện tại lớn hơn số nam thì sẽ cho Nhân ~1~ món quà;

• Nếu tổng số nam hiện tại bằng số nữ thì sẽ cho Phú ~1~ món quà;

Tính số món quà của mỗi bạn leader nhận được.

Input.

Một dòng duy nhất gồm một chuỗi chứa ký tự 'B', 'G' cho biết vị trí của các nam nữ. Độ dài của chuỗi không vượt quá ~10^5.~

Output.

Một dòng duy nhất gồm ba số cho biết số món quà của Trung, Nhân, Phú.

Sample input.

BGBGG

Sample output.

2 1 2

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.

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ố.

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

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ì.

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