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

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

Luna vừa được thầy Tina dạy về bài toán trò chơi nên rất hào hứng, đặc biệt trong đó có bài toán ăn kẹo thú vị như sau: Có hai người $A,B$ chơi trò chơi ăn kẹo, trên bàn có một đống $n$ viên kẹo và ai ăn được cái kẹo cuối cùng thì chiến thắng. Mỗi lượt cho phép ăn $1,2,...,k$ viên và $A$ sẽ đi trước. Theo các lý thuyết trò chơi thì ta biết rằng:

• Điều kiện để $B$ thắng là $n$ chia hết cho $k+1.$

• Điều kiện để $A$ thắng là $n$ không chia hết cho $k+1.$

Luna đã rất thuộc bài. Tuy nhiên thầy Tina đổi luật lại như sau: vẫn $n$ viên kẹo như trên nhưng ở lượt đầu tiên, $A$ được quyền chọn một số nguyên dương $k<n$ và ăn $k$ viên kẹo (số $k$ sẽ không thay đổi kể từ đó). Tiếp theo đến $B$ ăn và cứ thế, mỗi lượt ăn một số kẹo từ $1\to k$ . Hỏi $A$ nên chọn những số $k$ nào để có chiến lược thắng trò chơi này? Trường hợp không có số nào thì in ra $-1.$

Input: một dòng duy nhất gồm số nguyên dương $n$ với $2\le n\le {10}^9.$

Output: giá trị các số $k$ thỏa mãn, theo thứ tự từ nhỏ đến lớn.

Sample input:

5

Sample output:

1 2

Giải thích:

Nếu lượt đầu $A$ ăn $1$ viên thì còn $4$ viên. Tiếp theo, $B,A$ sẽ thay viên nhau ăn mỗi lần $1$ viên và $A$ sẽ ăn được viên cuối nên thắng.

Nếu lượt đầu $A$ ăn $2$ viên thì còn $3$ viên. Tiếp theo, $B$ ăn $1$ hoặc $2$ viên thì $A$ đều có thể ăn hết phần kẹo còn lại.

Nếu $A$ chọn $k=3,4$ thì dễ thấy sẽ thua trò chơi này.

Tại một khu bảo tồn tự nhiên, có $n$ quần thể động vật khác nhau trong đó quần thể thứ $i$ có $a_i$ sinh vật.

Hiện nay do thiếu thốn về thức ăn cho các động vật ở khu bảo tồn, nên ban lãnh đạo quyết định giảm thiểu $k$ sinh vật trong khu bảo tồn nhưng vẫn đảm bảo số lượng sinh vật ở quần thể nhiều nhất sẽ chênh lệch ít nhất so với số sinh vật ở quần thể nhỏ nhất.

Input:

• Dòng đầu tiên chứa $2$ số nguyên dương $n$ và $k$. ($n\le {10}^5,k\le \sum a_i$)
• Dòng tiếp theo chứa $n$ số nguyên dương $a_i$ là số lượng sinh vật trong quần thể thứ $i$. ($a_i\le {10}^9$)

Output:

Một dòng duy nhất chứa số sinh vật chênh lệch nhỏ nhất giữa quần thể đông nhất và quần thể ít nhất sau khi giảm thiểu.

Sample input:

3 3
4 3 1

Sample output:

1

Một công ty nọ khi mới bắt đầu vận hành đã tính cho phép nhân viên ghi hai thời điểm bắt đầu làm và thời điểm kết thúc làm việc vào rồi gửi lại công ty. Nhưng vì quên dặn nhân viên mình phải ghi ngày bắt đầu trước và ngày kết thúc sau, nên một số nhân viên đã lợi dụng điều điều đó và đảo lại thứ tự của hai thời điểm.

Sau khi phạm sai lầm ban lãnh đạo của cty quyết định sẽ cho các nhân viên làm việc trong đoạn thời gian ít nhất giữa hai thời điểm đó.

Nhờ bạn hãy tính số giây ít nhất từ thời gian làm việc mà các nhân viên đã ghi ra.

Input:

Dòng duy nhất chứa một chuỗi có dạng "hh:mm:ss dow hh:mm:ss dow"

Trong đó:

• $hh$: là chỉ số giờ, $hh=$ {$00..23$}
• $mm$: là chỉ số phút, $mm=$ {$00..59$}
• $ss$: là chỉ số giây, $ss=$ {$00..59$}
• $dow$: là chỉ ngày trong tuần bằng tiếng anh, $dow=$ {Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday} ứng với lần lượt các ngày từ thứ hai đến chủ nhật.

Output:

Một dòng duy nhất chứa một số nguyên là số giây nhỏ nhất có thể giữa hai thời gian trên.

Sample input:

07:30:30 Monday 07:30:00 Monday

Sample output:

30

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

Cho một tam giác $X$ có các cạch lần lượt là $a,b,c$ và một hình vuông $Y$ có cạnh là $n$. Hãy cho biết hình vuông $Y$ có chứa được hình tam giác $X$ hay không ?

Luôn đảm bảo tam giác $X$ là tam giác có diện tích lớn hơn $0$.

Input:

Một dòng duy nhất chứa $4$ số nguyên dương lần lượt là $a,b,c,n$ ($a,b,c,n\le {10}^6$).

Output:

Một dòng duy nhất chứa $1$ kí tự là Y (Nếu hình $Y$ chứa được hình $X$) hoặc là N (Nếu hình $Y$ không chứa được hình $X$).

Sample input:

3 4 5 4

Sample output:

Y