Contest Sinh nhật LQDOJ lần 2 - 2022 - Div.2

Bạn được cho \(n\) từ \(s_{1}, s_{2}, ..., s_{n}\), \(s_{i}\) gồm các chữ cái tiếng Anh viết thường, các từ được ngăn cách nhau bởi dấu cách. Bạn hãy in ra từ viết tắt của \(n\) từ này, từ viết tắt được tạo thành bằng cách viết hoa liên tiếp các chữ cái đầu tiên của mỗi từ.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 100)\) - số lượng từ.
• Dòng thứ hai chứa \(n\) từ \(s_{1}, s_{2}, ..., s_{n}\) \((\forall i, |s_{i}| \leq 20)\).

Output

• in ra một dòng duy nhất là từ viết tắt.

Example

3
nguyen duc thuan

NDT

3
flower on stone

FOS

Chúng ta sẽ gọi một chuỗi có thể nhận được bằng cách nối hai chuỗi bằng nhau là một chuỗi nhân đôi. Ví dụ: xyzxyz và aaaaaa là chuỗi nhân đôi, trong khi ababab và xyzxy thì không là chuỗi nhân đôi.

Cho một chuỗi \(S\) bao gồm các chữ cái tiếng Anh viết thường. Tìm độ dài của chuỗi nhân đôi dài nhất có thể thu được bằng cách xóa một hoặc một vài ký tự từ cuối \(S\). Dữ liệu đảm bảo rằng luôn tạo được một chuỗi nhân đôi không rỗng.

Input

• Gồm 1 dòng duy nhất chứa chuỗi \(S\) \((1 \leq |S| \leq 1000)\) gồm các ký tự latin in thường.

Output

• In ra một dòng là độ dài của chuồi nhân đôi.

Example

fosfosndt

6

Một con ếch có thể nhảy theo bước với một trong hai kiểu sau: Bước ngắn có độ dài \(1\), bước dài có độ dài \(b\).

Con ếch muốn nhảy về phía trước theo đường thẳng, sao cho sau đúng \(t\) bước nhảy con ếch đi được quãng đường độ dài \(d\).

Hỏi con ếch có thể làm được điều này hay không.

Input

• Gồm một dòng duy nhất với ba số \(d\), \(t\) và \(b\) \((1 \leq d \leq 10^{18}, 1 \leq t, b \leq 10^9)\).

Output

• In ra ''Possible'' nếu con ếch có thể nhảy chính xác \(t\) bước để có được độ dài chính xác là \(d\), hoặc ''Impossible'' nếu con ếch không thể làm được điều này.

Example

10 6 3 

Possible

10 5 3

Impossible

Cho một đồ thị vô hướng gồm \(n\) đỉnh và \(m\) cạnh. Các đỉnh được đánh số từ \(1\) đến \(n\). Các cạnh được đánh số từ \(1\) đến \(m\). Cạnh thứ \(i\) nối hai đỉnh \(a_i\) và \(b_i\), trên cạnh này có ghi một kí tự \(c_i\).

Một ''đường đi'' trên đồ thị có thể được biểu diễn bởi dãy số \(v_0, e_1, v_1, e_2, v_2, \ldots, v_{k-1}, e_k, v_k\), trong đó với mọi \(1 \leq i \leq k\), ta luôn có:

• \(1 \leq v_{i-1}, v_i \leq n\),
• \(1 \leq e_i \leq m\),
• Cạnh thứ \(e_i\) có hai đỉnh kề là \(v_{i-1}\) và \(v_i\).

Khi đó, đường đi này xuất phát ở đỉnh \(v_0\) và kết thúc ở đỉnh \(v_k\). Chú ý rằng các đỉnh \(v_0, v_1, \ldots, v_k\) hay các cạnh \(e_1, e_2, \ldots, e_k\) không nhất thiết phải đôi một phân biệt. Nói cách khác, một đường đi có thể đi qua một đỉnh hay một cạnh nhiều hơn một lần. Do mỗi cạnh của đồ thị có chứa một kí tự, ta viết lần lượt các chữ cái có trên các cạnh theo thứ tự của đường đi, và tạo ra xâu kí tự \(S = c_{e_1} c_{e_2} \ldots c_{e_k}\). Xâu kí tự này được gọi là ''xâu biểu diễn'' đường đi.

Cho đồ thị ở trên, bạn cần tìm ra đường đi ngắn nhất (chứa ít cạnh nhất) từ đỉnh \(1\) tới đỉnh \(2\), sao cho xâu biểu diễn của đường đi này là một xâu đối xứng.

Nhắc lại, xâu đối xứng là xâu kí tự mà khi đọc ngược hay xuôi đều như nhau. Ví dụ, a, ahiha hay abba là các xâu đối xứng; nhưng na, ahihi hay huhu thì không.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((2 \leq n \leq 20, 2 \leq 2 \cdot m \leq n \cdot (n - 1))\) lần lượt là số đỉnh và số cạnh của đồ thị.

• Trong \(m\) dòng còn lại, dòng thứ \(i\) chứa hai số nguyên \(a_i\), \(b_i\) \((1 \leq a_i, b_i \leq n)\) và một chữ cái Lattin in thường \(c_i\) thể hiện cạnh thứ \(i\) của đồ thị.

Output

• In ra một số nguyên duy nhất là độ dài (tính theo số cạnh) của đường đi ngắn nhất từ đỉnh \(1\) đến đỉnh \(2\) có xâu biểu diễn là xâu đối xứng. Nếu không tồn tại đường đi như vậy, in ra \(-1\).

Example

5 5
3 1 a
3 2 b
1 4 x
4 5 y
5 2 x 

3

5 5
3 1 a
3 2 b
1 4 x
4 5 y
5 2 z 

-1

Cho \(N\) điểm, đếm số cặp điểm thỏa mãn tồn tại một hình chữ nhật có cạnh song song với trục tọa độ
mà chứa cả hai điểm (có thể nằm trên cạnh) và không chứa bất kì điểm nào khác trong các điểm đã cho.

Input

• Dòng đầu chứa số \(N\) \((1 ≤ N ≤ 3·10^5)\)
• \(N\) dòng tiếp theo mỗi dòng chứa hai số \(x, y\) mô tả tọa độ của \(N\) điểm \((|x|, |y| \leq 10^9)\)

Output

• Đưa ra số cặp điểm thỏa mãn.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \leq 500\)
• Subtask \(2\) (\(20\%\) số điểm): \(N \leq 4000\)
• Subtask \(3\) (\(20\%\) số điểm): \(N \leq 10^4\)
• Subtask \(4\) (\(20\%\) số điểm): không có hai điểm nào nằm trên cùng một đường thẳng song song với một trong hai trục tọa độ
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

6
-1 -1
1 1
1 0
-1 0
-2 0
2 2 

5