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

Note

Đề gốc thi thử duyên hải 2021 lần 1

Ở 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 \leq n \leq 100000~, ~0 \leq m \leq 200000)~.

Mỗi dòng trong ~m~ dòng tiếp theo ghi ~2~ số ~a_i~ và ~b_i~ ~(1 \leq a_i~, ~b_i~ ~\leq n~, ~a_i \neq 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

Note

Đề gốc thi thử duyên hải 2021 lần 1

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 \dots~. 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 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. Nếu ký tự cuối của hàng không phải là ".", và ký tự đầu của hàng tiếp theo (theo vòng tròn) cũng không phải là "." thì cần nối từ cuối của hàng đó với từ đầu của hàng tiếp theo.

Input

Dòng đầu tiên ghi số nguyên ~m~ ~(1 \leq m \leq 2000)~ - số từ trong từ điển.

• Sau đó ~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 \leq n \leq 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

Note

Đề gốc thi thử duyên hải 2021 lần 1

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 \leq d_2 \leq d_3~;
• ~(d_1 + d_2)^2 - 1~ chia hết cho ~d_3~;
• ~(d_2 + d_3)^2 - 1~ chia hết cho ~d_1~;
• ~(d_3 + d_1)^2 - 1~ chia hết cho ~d_2~.

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

Dòng đầu tiên ghi số nguyên ~k~ ~(1 \leq k \leq 60000)~.

Output

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

Sample Input

1

Sample Output

2 2 3

Note

Đề gốc thi thử duyên hải 2021 lần 1

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 \leq n \leq 100000~; ~1 \leq A~, ~B \leq n~; ~A \leq B)~.

~n~ - ~1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~ và ~c~ ~(1 \leq u~, ~v \leq n~; ~u \leq v~; ~1 \leq c \leq 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 đường mới.

Sample Input

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

Sample Output

15

Note

Đề gốc thi thử duyên hải 2021 lần 1