Từ thời cổ đại, mỗi chiến binh có một bộ ba loại vũ khí: một thanh kiếm laser, một lưỡi dao laser và một dao găm laser để trát bơ trên bánh mì (khi đói).

Những vũ khí này có ràng buộc về độ dài như sau:

• Chiều dài dao găm - ~d_1~, chiều dài của lưỡi dao - ~d_2~, chiều dài của thanh kiếm - ~d_3~ đều là các số nguyên tố
• ~d_1 \le d_2 \le d_3~
• ~(d_1 + d_2)^2 - 1~ chia hết cho ~d_3~
• ~(d_1 + d_3)^2 - 1~ chia hết cho ~d_2~
• ~(d_2 + d_3)^2 - 1~ chia hết cho ~d_1~

Công ty bán bất kỳ bộ vũ khí theo số thứ tự từ điển. Cụ thể, sắp xếp tất cả các bộ theo ~d_1~ không giảm, nếu ~d_1~ như nhau thì xét ~d_2~ không giảm, và nếu ~d_1~ và ~d_2~ bằng nhau thì xét ~d_3~ tăng và đánh số chúng theo thứ tự từ ~1~ đến vô cùng.

Cho ~k~, hãy mua tập vũ khí thứ ~k~ theo thứ tự này.

Input: Một dòng duy nhất ghi số nguyên ~k (1 ≤ k ≤ 60000)~.

Output: In ra độ dài 3 loại vũ khí trong tập thứ ~k~.

Sample Input

1

Sample Output

2 2 3

Nguồn: 2021 Thi thử

Vương quốc chuẩn bị tổ chức một cuộc thi chạy việt dã. Mạng lưới đường sá của vương quốc bao gồm ~n - 1~ đường hai chiều kết nối ~n~ tỉnh. Giữa hai tỉnh bất kì đều có thể đi đến được với nhau thông qua những con đường này. Cuộc thi chạy sẽ có điểm xuất phát là tỉnh A (kinh đô) và điểm đích là tỉnh B (cố đô).

Do công tác bảo trì đường sá không được quốc vương chú trọng, các con đường này đã xuống cấp trầm trọng. Nếu chỉ đi bộ thì không có vấn đề gì, tuy nhiên, đây lại là một cuộc thi chạy. Mỗi con đường chỉ có thể chịu được một số lượng người nhất định chạy qua nó mà thôi.

Quốc vương vì muốn nhiều người được tham gia cuộc thi chạy nhất nên quyết định xây thêm một con đường mới (với chất lượng rất tốt, bao nhiêu người chạy qua cũng không hỏng). Tuy nhiên, con đường này không được phép nối trực tiếp đến kinh đô và cũng không được phép nối trực tiếp đến cố đô. Hãy giúp quốc vương tính xem sau khi xây dựng con đường mới, sẽ có tối đa bao nhiêu người có thể tham gia vào cuộc thi chạy?

Input:

• Dòng đầu tiên chứa ba số nguyên ~n, A~ và ~B (4 ≤ n ≤ 100000; 1 ≤ A, B ≤ n; A ≤ B)~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u, v~ và ~c (1 ≤ u, v ≤ n; u ≤ v; 1 ≤ c ≤ 1000)~ cho biết có một con đường hai chiều nối hai tỉnh ~u~ và ~v~, có tối đa ~c~ người có thể chạy qua con đường này.

Output: In ra số lượng tối đa người có thể tham gia cuộc thi chạy sau khi quốc vương xây thêm một con đườngmới.

Sample Input

4 1 4
1 2 10
1 4 10
3 4 5

Sample Output

15

Nguồn: 2021 Thi thử

Trái ngược với câu nói nổi tiếng "diêm không phải đồ chơi của trẻ em", nhưng bé An rất thích chơi diêm. Nhưng bé thích chơi xếp hình.

Mẹ cho bé nhiều hộp diêm, mỗi hộp có ~12~ que diêm. Bây giờ bé quan tâm: từ những que diêm với độ dài khác nhau, liệu có thể sắp xếp chúng thành hình hộp chữ nhật bằng keo? Không được bẻ que diêm và chúng không được nhô ra ngoài

Input: Dữ liệu đầu vào không quá ~1000~ hộp diêm, mỗi hộp gồm ~12~ số nguyên dương không vượt quá ~10^9~ . Đầu vào kết thúc bằng một chuỗi gồm ~12~ số ~0~ (không cần phải được xử lý).

Output: Đối với mỗi bộ diêm in ra "yes", nếu có thể dán chúng thành hình hộp chữ nhật và "no" trong trường hợp ngược lại.

Sample Input

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

Sample Output

yes
no

Nguồn: 2021 Thi thử

Trong quá trình khai quật khu định cư của một nền văn minh cổ đại, người ta đã phát hiện ra cư dân thời đó, cũng như những người hiện đại, đã uống đồ uống từ những chiếc chai có dán nhãn với thông tin về thức uống ghi trên chai. Một trong những nhãn này thậm chí còn tồn tại cho đến ngày nay.

Vấn đề là nền văn minh này không sử dụng dấu hiệu chuyển đổi. Ngay sau khi kết thúc dòng, người ta tiếp tục đọc dòng kế tiếp. Khi đọc sách, điều này không gây bất tiện, tuy nhiên, nhãn hiệu khác sách - nhãn đã được dán vào chai hình trụ, trên đó văn bản được viết trên một vòng tròn. Khi đọc văn bản, cần bắt đầu đọc dòng đầu tiên từ nơi dán keo, đọc cho đến khi chạm vào vị trí dán keo, đọc sang dòng thứ ~2~, rồi dòng thứ ~3~….. Nhưng các nhà khoa học vẫn không thể xác định nơi dán keo! Coi văn bản là một tập hợp các chuỗi có cùng độ dài ~k~, gồm các chữ cái và ký hiệu "." (đó là dấu cách trong nền văn minh này).

May mắn thay, bên cạnh nhãn, có một từ điển liệt kê tất cả những từ có thể được sử dụng ở nền văn minh này. Bây giờ, với những dữ liệu này, bạn cần xác định có bao nhiêu biến thể của vị trí dán keo. Cụ thể hơn, bạn cần phải xác định tất cả những giá trị không âm ~t < k~ sao cho ở mỗi hàng, nối các ký tự trong hàng đó (theo vòng tròn), bắt đầu từ vị trí thứ ~t~, thu được một tập hợp các từ trong từ điển, các từ cách nhau một hoặc nhiều ký tự ~"."~..

Input:

• Dòng đầu tiên ghi số nguyên ~m (1 ≤ m ≤ 2000)~ - số từ trong từ điển. Sau đấy ~m~ dòng ghi các từ trong từ điển. Tất cả các từ đều khác nhau, chỉ gồm chữ cái viết thường trong bảng chữ cái Latinh, độ dài của mỗi từ không vượt quá ~2000~ ký tự.
• Dòng tiếp theo ghi một số nguyên ~n (1 ≤ n ≤ 2000)~ - số dòng ghi trên nhãn. Các dòng trong ~n~ dòng tiếp theo ghi các chuỗi ký tự được viết trên nhãn. Tất cả các dòng này chỉ gồm các chữ cái viết thường trong bảng chữ cái Latinh và ký tự ".". Chiều dài của tất cả các dòng như nhau và không vượt quá ~2000~ ký tự. Đảm bảo mỗi dòng ghi ít nhất một ký tự ".".

Output: Dòng đầu tiên ghi số lượng các giá trị của ~t~. Dòng kế tiếp in ra các giá trị này được sắp xếp theo thứ tự tăng dần.

Sample Input:

2
uu
u
5
.uu..uu
.uu...u
...uu.u
.u.u.uu
uuu.uu.

Sample Output:

2
1 2

Ở một số quốc gia có ~n~ thành phố và ~m~ con đường giữa chúng. Hệ thống đường bộ được tổ chức như sau:

• Giữa hai thành phố không quá một con đường;
• Không có con đường kết nối thành phố với chính nó.

Chính phủ quyết định thực hiện cải cách hệ thống đường sá như sau:

• Phá hủy một trong những con đường hiện có;
• Xây dựng một con đường mới không có trước đó, con đường này không dẫn từ thành phố đến chính nó.

Ngoài ra, để cải thiện mối quan hệ kinh tế giữa các thành phố, chính phủ muốn sau khi cải cách, có thể đi đường bộ giữa bất kỳ ~2~ thành phố nào. Không đảm bảo rằng yêu cầu này được đáp ứng trước khi cải cách.

Hãy giúp chính phủ xác định xem có bao nhiêu cách cải cách.

Input: Dòng đầu tiên ghi ~2~ số nguyên ~n~ và ~m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 200000)~. Mỗi dòng trong ~m~ dòng tiếp theo ghi ~2~ số ~a_i~ và ~b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i)~ - số thứ tự ~2~ thành phố đầu mút của con đường thứ ~i~.

Output: In ra số cách cải cách.

Sample Input:

4 4
1 2
2 3
1 3
3 4

Sample Output:

8

Nguồn: 2021 Thi thử