Cho ~3~ điểm tọa độ nguyên trên lưới tọa độ ~Oxy~, hãy xác định xem ~3~ điểm này có tạo thành hình tam giác được hay không?

Input

• ~3~ điểm có tọa độ nguyên.

Output

• In ra ~0~ nếu ~3~ điểm đã cho không thể tạo được một tam giác, ngược lại in ra ~1~.

Constraints

• Tọa độ của ~3~ điểm đều là số nguyên trong khoảng ~[-10^9,10^9]~.

Sample Input 1

0 0 0 1 1 0

Sample Output 1

1

Sample Input 2

727 1 727 2 727 3

Sample Output 2

0

Cho một đa giác lồi ~n~ đỉnh, các đỉnh được nhập theo thứ tự ngược chiều kim đồng hồ.

Hãy tính diện tích của đa giác lồi đã cho.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~ trên đa giác.

Output

• In ra kết quả của bài toán lấy đến số thập phân thứ nhất.

Constraints

• ~1 \le n \le 10^2~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Sample Input 1

4
6 1
7 4
2 5
1 1 

Sample Output 1

18.0

Trên hệ tọa độ ~Oxy~, cho một đa giác lồi gồm ~n~ đỉnh. Có ~m~ truy vấn, mỗi truy vấn gồm một điểm, hãy kiểm tra xem điểm đó có nằm trong đa giác đã cho hay không.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~ trên đa giác. Các đỉnh được nhập vào theo thứ tự ngược chiều kim đồng hồ.
• Dòng tiếp theo gồm số nguyên dương ~m~.
• ~m~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thuộc truy vấn ~i~.

Output

• Gồm ~m~ dòng, dòng ~i~ in ra ~0~ nếu điểm thứ ~i~ không nằm trong đa giác, ngược lại in ra ~1~.

Constraints

• ~1 \le n,m \le 10^3~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Sample Input 1

4
2 4
8 4
6 8
4 6
4
3 5
4 7
5 5
6 7

Sample Output 1

0
0
1
1

Trên hệ trục tọa độ ~Oxy~, cho điểm ~P~ có tọa độ nguyên và ~n~ đường thẳng, đường thẳng thứ ~i~ đi qua ~2~ điểm ~A_i~ và ~B_i~.

Hãy tính độ dài dài nhất của khoảng cách từ điểm ~P~ tới một trong các đường thẳng đã cho.

Input

• Dòng đầu gồm hai số nguyên ~x_P~ ~y_P~ miêu tả tọa độ của điểm ~P~.
• Dòng thứ hai chứa số nguyên dương ~n~ miêu tả số đường thẳng.
• ~n~ dòng sau, dòng thứ ~i~ gồm ~4~ số nguyên dương ~x_A, y_A, x_B, y_B~ miêu tả tọa độ của hai điểm ~A,B~ mà đường thẳng ~i~ đi qua.

Output

• In ra kết quả của bài toán với độ chính xác ~2~ chữ số sau dấu phẩy.

Constraints

• ~n \le 10^3~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Sample Input 1

0 0
3
1 2 4 6
2 3 5 7
1 4 7 8

Sample Output 1

2.77

Sample Input 2

1 3
4
1 2 4 6
-1 -3 5 7
-2 4 -3 6
0 0 5 9

Sample Output 2

2.24

Trên hệ trục tọa độ ~Oxy~, cho điểm ~P~ có tọa độ nguyên và ~n~ đoạn thẳng, đoạn thẳng thứ ~i~ có ~2~ đầu mút là ~A_i~ và ~B_i~.

Hãy tính độ dài dài nhất của khoảng cách ngắn nhất từ điểm ~P~ tới một trong các đoạn thẳng đã cho.

Input

• Dòng đầu gồm hai số nguyên ~x_P~ ~y_P~ miêu tả tọa độ của điểm ~P~.
• Dòng thứ hai chứa số nguyên dương ~n~ miêu tả số đường thẳng.
• ~n~ dòng sau, dòng thứ ~i~ gồm ~4~ số nguyên dương ~x_A, y_A, x_B, y_B~ miêu tả tọa độ của hai điểm ~A,B~ là đầu mút của đoạn thẳng ~i~.

Output

• In ra kết quả của bài toán với độ chính xác ~2~ chữ số sau dấu phẩy.

Constraints

• ~n \le 10^3~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Sample Input 1

0 0
3
1 2 4 6
2 3 5 7
1 4 7 8

Sample Output 1

4.12

Sample Input 2

1 3
4
1 2 4 6
-1 -3 5 7
-2 4 -3 6
0 0 5 9

Sample Output 2

3.16

Trên trục tọa độ ~Oxy~, cho tọa độ điểm ~I~. Có ~n~ đoạn thẳng và một số nguyên ~k~, đoạn thứ ~i~ có hai đầu mút là ~2~ điểm ~A_i~ và ~B_i~. Đường tròn có tâm ~I~ và bán kính ~R~ với ~R~ là số nguyên không âm, gọi tắt là ~(I,R)~, được gọi là tốt nếu chỉ có bé hơn hoặc bằng ~k~ đoạn thẳng có điểm nằm bên trong hoặc bên trên đường tròn.

Hãy tìm số nguyên không âm ~R~ lớn nhất sao cho đường tròn ~(I,R)~ là tốt.

Input

• Dòng đầu gồm hai số nguyên ~x_I,y_I~ miêu tả tọa độ của điểm ~I~.
• Dòng thứ hai gồm ~2~ số nguyên dương ~n~ và ~k~.
• ~n~ dòng sau, mỗi dòng gồm hai cặp số nguyên: ~x_{A_i},y_{A_i}~ và ~x_{B_i},y_{B_i}~ là hai đầu mút của đoạn thẳng thứ ~i~.

Output

• In ra ~R~ là kết quả của bài toán.

Constraints .

• ~1 \le k < n \le 10^5~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Subtask

• Sub ~1~ (~50\%~): ~n \le 1000~ và tọa độ của các điểm đều nằm trong khoảng ~[-10^3,10^3]~.
• Sub ~2~ (~50\%~): Không giới hạn gì thêm.

  Sample Input 1

0 0
4 2
-4 4 1 5
-3 2 -1 1
2 2 6 4
-3 -2 -1 -4

Sample Output 1

3

Explanation 1

Đường tròn tâm ~A~ với bán kính là ~3~ gồm ~2~ đoạn thẳng có điểm nằm bên trong hoặc bên trên đường tròn là ~DE~ và ~FG~, đây là bán kính lớn nhất thỏa mãn.

Cho ~n~ điểm trên mặt phẳng ~Oxy~. Hãy đếm số tam giác vuông được tạo thành từ ~3~ trong số ~n~ điểm trên.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~.

Output

• In ra số tam giác vuông được tạo thành.

Constraints .

• ~1 \le n \le 1500~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Subtask

• Sub ~1~ (~50\%~): ~n \le 200~.
• Sub ~2~ (~50\%~): Không giới hạn gì thêm.

Sample Input 1

5
-1 1
-1 0
0 0
1 0
1 1

Sample Output 1

7

Cho ~n~ điểm trên mặt phẳng ~Oxy~. Hãy đếm số bộ ba điểm thẳng hàng.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~.

Output

• In ra số bộ ba điểm thẳng hàng.

Constraints .

• ~1 \le n \le 2000~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^4,10^4]~.

Subtask

• Sub ~1~ (~50\%~): ~n \le 200~.
• Sub ~2~ (~50\%~): Không giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

3

Cho ~n~ điểm trên mặt phẳng ~Oxy~ và tham số ~p~.

Hãy xác định xem, có tồn tại một đường thẳng sao cho có ít nhất ~p~ phần trăm các điểm trong ~n~ điểm được cho nằm chính xác trên đường thẳng đó hay không.

Input

• Dòng đầu gồm số nguyên dương ~t~ miêu tả số bộ test.
• Mỗi bộ test bao gồm:
  • Dòng đầu gồm số nguyên dương ~n~.
  • Dòng thứ hai gồm số nguyên dương ~p~.
  • ~n~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~.

Đảm bảo rằng không có hai điểm nào trùng khớp.

Output

• Với mỗi bộ test, nếu tồn tại đường thẳng thỏa mãn thì in ra "possible", ngược lại in ra "impossible".

Constraints .

• ~1 \le t \le 5~.
• ~1 \le n \le 10^5~.
• ~35 \le p \le 100~
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^9,10^9]~.

Subtask

• Sub ~1~ (~50\%~): ~n \le 1000~.
• Sub ~2~ (~50\%~): Không giới hạn gì thêm.

Sample Input 1

2
5
55
0 0
10 10
10 0
0 10
3 3
5
45
0 0
10 10
10 0
0 10
3 4

Sample Output 1

possible
impossible

Explanation 1

Ở ví dụ ~1~, tồn tại đường thẳng đi qua (ít nhất) ~3~ điểm trong số ~5~ điểm trên.

Ở ví dụ ~2~, không tồn tại đường thẳng nào đi qua nhiều hơn hoặc bằng ~45\%~ số điểm.

Trên hệ trục toạ độ ~Oxy~, cho một đa giác lồi được tạo bởi ~N~ điểm có toạ độ nguyên.

Yêu cầu: Hãy tìm hình tứ giác có diện tích lớn nhất được tạo bởi ~4~ trong ~N~ điểm của đa giác lồi đã cho.

Dữ liệu vào từ tệp văn bản QUADIL.INP:

• Dòng thứ nhất ghi số ~N~ ~(4 \le N \le 10^4)~ là số đỉnh của đa giác lồi;
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ ~(|x|, |y| \le 10^5)~ biểu diễn toạ độ các đỉnh của đa giác. Thứ tự các đỉnh được liệt kê theo chiều kim đồng hồ.

Kết quả ghi ra tệp văn bản QUADIL.OUT:

Gồm một số duy nhất là diện tích lớn nhất của tứ giác tìm được. Kết quả lấy chính xác ~1~ chữ số sau phần thập phân.

Ví dụ

Input

5
0 2
1 3
2 2
2 0
0 0

Output

4.0

Giải thích

Chọn các đỉnh: ~(0, 2), (2, 2), (2, 0), (0, 0)~.

Input

6
4 2
3 3
4 5
6 5
7 3
6 2

Output

6.5

Giải thích

Chọn các đỉnh: ~(3, 3), (4, 5), (6, 5), (6, 2)~.

Ràng buộc

• Có ~40\%~ số test ứng với ~40\%~ số điểm có ~N \le 50~;
• ~30\%~ số test khác ứng với ~30\%~ số điểm có ~N \le 200~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N \le 2000~;
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm không có ràng buộc gì thêm.

Trên mặt phẳng tọa độ, cho ~n~ điểm có tọa độ nguyên. Hãy tính chu vi của bao lồi của tập điểm này.

Input

• Dòng đầu gồm số nguyên dương ~n~ là số điểm.
• ~n~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~x_i,y_i~ là tọa độ của điểm thứ ~i~.

Output

• In ra chu vi của bao lồi của tập điểm, kết quả lấy chính xác tới ~1~ chữ số thập phân.

Constraints

• ~3 \le n \le 10^4~.
• ~-10^4 \le x_i,y_i \le 10^4~.

Sample Input 1

6    
1 1    
2 5    
3 3    
5 3    
3 2    
2 2

Sample Output 1

12.2

Explanation 1

Bao lồi cần tìm gồm ~3~ điểm ~(1,1),(2,5),(5,3)~, có chu vi là ~12.200792856~.

Cho ~n~ điểm trên trục tọa độ ~Oxy~, hãy tìm bao lồi gồm nhiều đỉnh nhất của tập điểm đã cho.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ là số điểm.

• ~n~ dòng sau, mỗi dòng chứa ~2~ số ~x_i,y_i~ miêu tả tọa độ điểm thứ ~i~.

  Output

• In ra số đỉnh của bao lồi cần tìm.

Constraints

• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Sample Input 1

5
2 1
2 3
2 5
6 3
4 3

Sample Output 1

4

Explanation 1

Các đỉnh ~A,B,C,D~ nằm trong bao lồi cần tìm.

~3~ đỉnh ~A,C,D~ cũng tạo ra một bao lồi, tuy nhiên số đỉnh của nó không phải là tối đa.

~ABC~ đã được bầu làm Thị trưởng ~NoLand~ và cần xây dựng một khu vực để tổ chức cuộc họp liên quan đến các vấn đề của ~NoLand~.

Anh ấy yêu cầu một nhóm thợ xây đào ~n~ cái hố để cắm ~r~ cọc vào khu đất. Các cọc phải được đặt sao cho toàn bộ khu vực (tất cả các hố đã đào) đều được che phủ.

Chỉ có ~r~ cọc, anh ta có thể xây hội trường không?

Input

• Dòng đầu là số nguyên dương ~t~ - số test case.
• Với mỗi test case, dòng đầu chứa ~2~ số nguyên dương ~n,r~ là số hố và số cọc.

• ~n~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~x_i,y_i~ là tọa độ của các hố.

  Output

• Với mỗi test case, in ra ~0~ nếu không thể xây dựng hội trường, ngược lại in ra ~1~.

Constraints

• ~1 \le T \le 10~.
• ~3 \le n \le 10^4~.
• ~-10^5 \le x_i,y_i \le 10^5~.

Sample Input 1

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

Sample Output 1

1

Ở một nông trại nọ, có ~n~ cái cọc. Để bảo vệ con cừu của mình, bác nông dần cần dựng lên các rào chắn, sau đó đặt nó vào vị trí được bao bởi nhiều rào chắn nhất. Mỗi rào là một đa giác không tự cắt được tạo ra bằng cách nối các cái cọc lại với nhau bằng dây thừng, mỗi cái cọc thuộc không quá ~1~ rào chắn. Các rào phải được tạo ra sao cho với mỗi cặp rào chắn bất kì ~X~ và ~Y~ thì diện tích chung của ~X~ và ~Y~ là ~min (S(X), S(Y))~ hoặc ~0~.

Trên mặt phẳng tọa độ, các cái cọc được coi như các điểm với tọa độ nguyên. Hãy xác định xem con cừu sẽ được bảo vệ bởi tối đa bao nhiêu rào chắn.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng tiếp theo, lần lượt mỗi dòng chứa ~2~ số là tọa độ của các cọc.

Output

• In ra số nguyên duy nhất là kết quả của bài toán.

Constraints

• ~1 \le n \le 2000~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^4,10^4]~.

Sample Input 1

12
-9 -5
8 -4
-6 -4
0 -8
-4 -2
-3 -9
7 6
-2 9
-3 8
9 6
4 1
0 -7

Sample Output 1

2

Cho ~2~ tập điểm ~A~ và ~B~ trên trục tọa độ ~Oxy~. Một điểm của tập ~B~ được gọi là đẹp nếu vị trí của nó nằm trong một tam giác không suy biến (diện tích dương) có ba đỉnh thuộc tập điểm ~A~. Nếu điểm đó nằm trên cạnh của tam giác, ta cũng coi đó là một đỉnh tốt.

Yêu cầu: Cho biết tập điểm ~A~ và ~B~, hãy cho biết số điểm tốt của tập ~B~.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng tiếp theo, lần lượt mỗi dòng chứa ~2~ số là tọa độ của các điểm trong tập ~A~.
• Dòng tiếp theo gồm số nguyên dương ~k~.

• ~k~ dòng tiếp theo, lần lượt mỗi dòng chứa ~2~ số là tọa độ của các điểm trong tập ~B~.

  Output

• In ra số nguyên duy nhất là số điểm tốt của tập ~B~.

Constraints

• ~1 \le n,k \le 10^5~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^9,10^9]~.

Sample Input 1

6
1 2
1 5
3 1
3 3
5 2
5 3
4
2 2
3 4
4 2
4 5

Sample Output 1

3

Cho ~2~ tập điểm ~A~ và ~B~, hãy tìm một điểm trong tập ~A~ và một điểm trong tập ~B~ sao cho khoảng cách giữa chúng là lớn nhất, biết khoảng cách từ điểm ~a~ tới điểm ~b~ là ~\sqrt {(a.x-b.x)^2+(a.y-b.y)^2}~.

Input

• Dòng đầu gồm số nguyên dương ~n~ là số lượng điểm của cả ~2~ tập.

• ~n~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên ~x_i,y_i,c_i~ ~(-10^6 \le x_i,y_i \le 10^6, 0 \le c_i \le 1)~. Với ~x_i,y_i~ là tọa độ của điểm thứ ~i~ và ~c_i = 0~ nếu điểm này thuộc tập ~A~, ngược lại ~c_i = 1~ nếu điểm này thuộc tập ~B~. Đảm bảo rằng mỗi tập có ít nhất một điểm.

  Output

• In ra số nguyên duy nhất là khoảng cách xa nhất giữa ~2~ điểm trong các điểm đã cho. Kết quả lấy theo phần nguyên.

Constraints

• ~1 \le n \le 50000~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Subtask

• ~50\%~ số điểm có ~n \le 2000~.
• ~50\%~ còn lại không ràng buộc gì thêm.

Sample Input 1

5
1 5 1
-5 2 0
3 7 1
6 -2 0
5 1 0

Sample Output 1

9

Cho ~n~ điểm trên mặt phẳng tọa độ, hãy tìm ~3~ điểm sao cho chúng tạo thành một tam giác không suy biến và diện tích của nó là lớn nhất có thể.

Input

• Dòng đầu gồm số nguyên dương ~n~ là số lượng điểm.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên ~x_i,y_i~ ~(-10^7 \le x_i,y_i \le 10^7)~. Với ~x_i,y_i~ là tọa độ của điểm thứ ~i~.

Output

• In ra số nguyên duy nhất là diện tích tam giác lớn nhất được tạo thành từ ~3~ điểm trong các điểm đã cho. Kết quả lấy chính xác tới chữ số thập phân thứ nhất.

Constraints

• ~3 \le n \le 3000~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^7,10^7]~.

Subtask

• ~50\%~ số điểm có ~n \le 200~.
• ~50\%~ còn lại không ràng buộc gì thêm.

Sample Input 1

5
3 6
2 7
1 8
4 9
1 4

Sample Output 1

6.0

Cho một dãy số nguyên ~a~ gồm ~n~ phần tử. Tập điểm ~S~ trên hệ trục tọa độ ~Oxy~ sẽ được xây dựng từ dãy ~a~, cụ thể hơn, nó bao gồm các điểm có tọa độ ~(a_i,a_j)~, ~\forall 1 \le i < j \le n~.

Gọi bao lồi của tập điểm ~S~ là ~C~, ~Area(C)~ là diện tích của ~C~, hãy tính ~2*Area(C)~.

Input

• Dòng đầu gồm số nguyên dương ~n~ là độ dài dãy ~a~.

• Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,...,a_n~.

  Output

• In ra ~2*Area(C)~, có thể chứng minh rằng đây là một số nguyên.

Constraints

• ~3 \le n \le 10^5~.
• ~1 \le a_i \le 10^8~.

Subtask

• ~50\%~ số điểm có ~n \le 1000~.
• ~50\%~ còn lại không ràng buộc gì thêm.

Sample Input 1

4
2 4 1 3

Sample Output 1

13

Explanation 1

Đa giác ~DCFEA~ chính là bao lồi của tập điểm và ~2*Area(C) = 2*6.5 = 13~

Hôm nay là sinh nhật ~ABC~ và ~DEF~ muốn chuẩn bị một chiếc bánh cho cô ấy. Anh ấy có ~n~ điểm ~(x_1, y_1), (x_2, y_2), …, (x_n, y_n)~ trong mặt phẳng hai chiều, và một cây nến được đặt ở một điểm trong mặt phẳng.

Số lớp của chiếc bánh là một số không âm. ~DEF~ coi độ ngon của chiếc bánh bằng với số lớp của chiếc bánh. Một lớp là một đa giác đơn với các đỉnh là một số điểm trong ~n~ điểm của ~DEF~. Với mỗi điểm của ~DEF~, nó không nhất thiết phải thuộc một lớp. Hơn nữa các lớp phải thỏa mãn các điều kiện sau:

• Với mỗi lớp, cây nến phải nằm hẳn bên trong nó
• Với mỗi điểm trong ~n~ điểm mà nằm hẳn trong một lớp, nó phải thuộc lớp khác hoặc có thể là điểm của cây nến
• Không có hai lớp nào chạm hoặc giao nhau
• Các lớp phải được chọn sao cho độ ngon của chiếc bánh là lớn nhất có thể

Bây giờ ~DEF~ tự hỏi, độ ngon của chiếc bánh phụ thuộc thế nào vào vị trí đặt nến. Bạn cần trả lời ~q~ truy vấn. Trong mỗi truy vấn, bạn được cho một điểm ~p = (x, y)~ là điểm mà ~DEF~ đặt nến và bạn cần tìm phải độ ngon của chiếc bánh

Input

• Dòng đầu gồm số nguyên dương ~n~ và ~q~.
• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i,y_i~.

• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x,y~ miêu tả truy vấn.

  Output

• Với mỗi truy vấn, in ra một dòng chứa số nguyên là độ ngon của bánh.

Constraints

• ~3 \le n \le 5000~.
• ~1 \le q \le 2000~.
• ~-10^9 \le x_i,y_i \le 10^9~.
• ~-10^9 \le x,y \le 10^9~.

Subtask

• ~50\%~ số điểm có ~1 \le n,q \le 200~.
• ~50\%~ còn lại không ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

0
1

Explanation 1

Trong truy vấn đầu tiên, ~p = (6, 6)~. Bánh không thể có lớp nào, nên độ ngon của nó là ~0~

Trong truy vấn thứ hai, ~p = (3, 3)~. Bánh chỉ có thể có một lớp, ví dụ là một tam giác với các đỉnh là ~(2, 1), (4, 1), (3, 4)~. Có những lựa chọn khác cho lớp này nhưng bánh không thể có nhiều hơn ~1~ lớp.

Tay săn ảnh trẻ tuổi nhưng đầy triển vọng ABC rất muốn trở nên nổi tiếng. Để làm được điều này, anh ấy muốn chụp ảnh một siêu sao mới nổi trong khi cô ấy đi dạo trên núi.

Được biết, quãng đường của ngôi sao đó trên núi gồm ~n~ đoạn. Với mỗi ~i~, đoạn đường thứ ~i~ là một khoảng nửa mở thẳng đứng có tọa độ ~x = i~ và ~y ∈ [0, hi)~.

Nếu ABC đứng ở vị trí ~j~ và người nổi tiếng ấy đứng ở vị trí ~i~, anh ta có thể chụp được cô khi và chỉ khi anh ta nhìn thấy cô, tức là ~i < j~ và với mọi ~i < k < j~, khoảng nửa mở tạo lên đoạn thứ ~k~ không được cắt đoạn ~[(i,j_i),(j,h_j)]~. ABC là một tay săn ảnh, dĩ nhiên không phải là một lập trình viên, vì vậy anh muốn bạn xác định khoảng cách tối đa mà anh ấy có thể chụp được ảnh ngôi sao nổi tiếng trên, tức là tìm là giá trị lớn nhất của ~j - i~ trên tất cả các cặp ~(i, j)~ thỏa mãn điều kiện. Hãy giúp anh ấy trở nên nổi tiếng!

Input

• Dòng đầu gồm số nguyên dương ~n~ là số lượng đoạn.
• Dòng thứ hai gồm ~n~ số nguyên ~h_1,h_2,...,h_n~.

Output

• In ra khoảng cách lớn nhất cần tìm.

Constraints

• ~3 \le n \le 10^5~.
• ~1 \le h_i \le 10^9~.

Subtask

• ~50\%~ số điểm có ~n \le 1000~.
• ~50\%~ còn lại không ràng buộc gì thêm.

Sample Input 1

7
3 2 5 3 2 4 3

Sample Output 1

3

Explanation 1

Cặp ~(3,7)~ không thỏa mãn do ~FN~ giao với ~KL~. Cặp ~(3,6)~ là một cặp thỏa mãn và cho ra kết quả tốt nhất.

Trên hệ trục tọa độ vuông góc ~Oxy~, cho tọa độ ~N~ điểm trong đó không có ba điểm nào thẳng hàng.

Yêu cầu: Tìm hai điểm trong ~N~ điểm để đường thẳng chứa hai điểm đó chia ~N-2~ điểm còn lại thành hai phần sao cho tổng số điểm của mỗi phần chênh lệnh nhau không quá ~1~.

Dữ liệu vào từ tệp văn bản DIVPOINT.INP:

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N ≤ 10^5)~ là số lượng điểm;
• ~N~ dòng sau, mỗi dòng chứa hai số nguyên ~x, y~ là toạ độ của một điểm ~(|x| ≤ 10^9~; ~\ |y| ≤ 10^9)~.

Kết quả ghi ra tệp văn bản DIVPOINT.OUT:

Một dòng gồm bốn số nguyên là toạ độ của hai điểm thoả mãn. Có thể có nhiều kết quả, ghi ra một kết quả bất kì.

Ràng buộc

• Có ~30\%~ số test ứng với ~N ≤ 100~;
• ~30\%~ số test khác ứng với ~N ≤ 5000~;
• ~40\%~ số test còn lại ứng với ~N ≤ 10^5~.

Ví dụ

Input

4
0 0
0 1
1 1
1 0

Output

0 0 1 1

Cho ~n~ điểm trên hệ trục tọa độ ~OXY~. Điểm thứ ~i~ gọi là ~P_i~.

Hai tam giác ~ABC~ và ~CDE~ được định nghĩa là bằng nhau nếu:

• ~AB = CD~
• ~BC = DE~
• ~AC = CE~
• ~\angle {BAC} = \angle {DCE}~
• ~\angle {ABC} = \angle {CDE}~
• ~\angle {ACB} = \angle {CED}~

Bạn cần đếm số bộ sáu số nguyên dương ~(i_1,i_2,i_3,j_1,j_2,j_3)~ sao cho chúng khác nhau đôi một và:

• ~1 \le i_1,i_2,i_3,j_1,j_2,j_3 \le n~
• ~i_1 < i_2 < i_3~
• ~\triangle {P_{i_1}P_{i_2}P_{i_3}}~ không suy biến, nói cách khác nó có diện tích dương.
• ~\triangle {P_{i_1}P_{i_2}P_{i_3}} = \triangle {P_{j_1}P_{j_2}P_{j_3}}~

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương ~x_i~ và ~y_i~ là tọa độ của điểm ~P_i~.

Constraints

• ~n \le 100~
• ~1 \le x_i , y_i \le 10^9~

Subtask

• Subtask ~1~: ~n,m \le 10~ ~(40\%)~
• Subtask ~2~: Không có giới hạn gì thêm ~(60\%)~

Output

• In ra số bộ sáu tìm được.

Sample Input 1:

6
2 2
4 6
6 2
14 8
10 6
14 4

Sample Output 1:

4

Explanation 1:

Ta có ~4~ bộ như sau:

• ~(1,2,3,4,5,6)~
• ~(1,2,3,4,6,5)~
• ~(4,5,6,1,2,3)~
• ~(4,5,6,1,3,2)~

Cho dãy ~a~ nguyên dương gồm ~n~ phần tử.

Bạn có thể thực hiện thao tác sau vô số lần:

• Chọn ra một đoạn ~[l,r]~ ~(1 \le l \le r \le n)~ và thay thế ~a_l = a_{l+1} = ... = a_r = \frac{a_l+a_{l+1}+...+a_r}{r-l+1}~. Ví dụ, nếu có dãy ~a = [1,3,6,7]~ và bạn chọn đoạn ~[2,3]~, ta sẽ thu được dãy ~a = [1,4.5,4.5,7]~.

Hãy in ra dãy ~a~ có thứ tự từ điển nhỏ nhất mà bạn có thể thu về được.

Dãy ~a~ có thứ tự từ điển bé hơn dãy ~b~ có cùng độ dài khi: gọi vị trí ~i~ là vị trí đầu tiên mà ~a~ và ~b~ khác nhau, ta có ~a_i < b_i~.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~.

Output

• Gồm ~n~ dòng, dòng thứ ~i~ in ra giá trị ~a_i~ của dãy ~a~ tốt nhất tìm được. Kết quả lấy ~9~ chữ số sau dấu phẩy.

Constraints .

• ~1 \le n \le 2\times10^5~
• ~1 \le a_i \le 10^6~

Subtask

• Sub ~1~ (~30\%~): ~n \le 20~.
• Sub ~2~ (~30\%~): ~n \le 2000~.
• Sub ~3~ (~40\%~): ~n \le 2\times10^5~.

  Sample Input 1

5
1 3 2 2 3

Sample Output 1

1.000000000
2.333333333
2.333333333
2.333333333
3.000000000

Explanation 1

Thực hiện ~1~ thao tác trên đoạn ~[2,3]~.

Cho một đồ thị có hướng không trọng số gồm ~n~ đỉnh và ~m~ cạnh. Bạn đang đứng ở đỉnh ~S~ của đồ thị và mục tiêu của bạn là đến được đỉnh ~T~. Tuy nhiên, khác với bình thường, mỗi bước đi của bạn chỉ có thể đi qua đúng ~3~ cạnh nối tiếp nhau bắt đầu từ đỉnh đang đứng. Ví dụ, có bốn cạnh ~(1,2), (2,3), (3,4), (3,5)~, khi đứng ở đỉnh ~1~ thì trong một bước bạn chỉ được đi tới đỉnh ~4~ hoặc ~5~.

Cho đỉnh ~S~ và ~T~ hãy tìm số bước đi ngắn nhất để từ đỉnh ~S~ tới được ~T~.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~n,m~, miêu tả số đỉnh và số cạnh.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u,v~ miêu tả cạnh một chiều ~u,v~.
• Dòng cuối gồm ~2~ số nguyên dương ~S~ và ~T~ miêu tả đỉnh xuất phát và đỉnh đích.

Output

• In ra một số là số bước ít nhất để đi từ ~S~ tới ~T~, nếu không có cách đi nào thì in ra ~-1~.

Điều kiện

• ~1 \le n,m \le 2*10^5~

Ví dụ

Input 1:

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

Output 1:

2

Input 2:

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

Output 2:

-1

Cho đồ thị đầy đủ vô hướng có trọng số (nghĩa là đồ thị gồm ~\frac{n*(n-1)}{2}~ cạnh phân biệt), trong đó có ~m~ cạnh có trọng số là ~1~, các cạnh còn lại có trọng số là ~0~.

Hãy tìm cây khung nhỏ nhất của đồ thị này.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, 1 \le m \le min(4*10^5,\frac{n*(n-1)}{2}))~
• ~m~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên ~u_i,v_i~ ~(1 \le u_i, v_i \le n, u_i \neq v_i)~ - miêu tả cạnh ~(u_i,v_i)~ có trọng số là ~1~.

Output:

• Trọng số của cây khung nhỏ nhất của đồ thị.

Constraints:

• Có ~50\%~ số test ứng với ~n \le 2*10^3~
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input 1

6 11
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6

Output 1

2

Input 2

3 0

Output 2

0

Đất nước ~ABC~ có ~n~ thành phố và ~m~ con đường hai chiều. Con đường thứ ~i~ nối hai thành phố ~u_i~ và ~v_i~ với nhau, có độ dài ~l_i~ và độ đẹp ~b_i~.

~H~ là một du khách. Hiện tại, anh đang ở thành phố ~1~ và cần đi tới thành phố ~n~ để dự sự kiện. Là một người đam mê cái đẹp, anh muốn chọn một lộ trình sao cho những con đường anh đi qua có tổng độ đẹp là lớn nhất, tuy vậy do cần tiết kiệm thời gian nên anh sẽ chỉ chọn lộ trình ngắn nhất (tức là tổng độ dài các con đường là bé nhất có thể) để đi từ ~1~ tới ~n~.

Hãy giúp ~H~ tính toán lộ trình ngắn nhất và có tổng độ đẹp lớn nhất mà anh ta có thể đi.

Input

• Dòng thứ nhất chứa ~2~ số nguyên dương ~n,m~.
• ~m~ dòng sau mỗi dòng gồm ~4~ số nguyên dương ~u_i,v_i,l_i,c_i~ ~(1 \le u, v \le n, u \neq v)~, miêu tả con đường nối thành phố ~u_i~ với ~v_i~ có độ dài ~l_i~ và độ đẹp ~c_i~.

Output

• Gồm một dòng chứa hai số nguyên ~L~ và ~B~, với ~L~ là độ dài của lộ trình ngắn nhất để đi từ ~1~ tới ~n~ và ~B~ là độ đẹp lớn nhất có thể của các lộ trình có độ dài ~L~.
• Nếu không có lộ trình nào để đi từ ~1~ tới ~n~, in ra ~-1~.

Constraints

• ~1 \le n,m \le 2*10^5~.
• ~1 \le l_i,c_i \le 10^9~.

Subtasks

• Subtask ~1~: ~1 \le n,m \le 20~ ~(30\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(70\%)~

Sample Input 1:

5 6
1 5 8 9
1 2 3 2
2 5 3 4
1 3 1 1
3 4 1 5
4 5 4 1

Sample Output 1:

6 7

Explanation 1:

Có hai lộ trình có độ dài ~6~ có thể đi là ~(1,2,5)~ và ~(1,3,4,5)~. Trong đó lộ trình ~(1,3,4,5)~ có độ đẹp lớn nhất là bằng ~7~.

Sample Input 2:

4 2
1 2 1 1
1 3 1 1

Sample Output 2:

-1

Explanation 2:

Không có lộ trình nào để đi từ ~1~ tới ~4~.

Mrtee đang lặn lội trên con đường tìm ma pháp sư Marisa thì có một con Rùa và một con Thỏ cãi nhau xem ai nhanh hơn. Chúng quyết định giải quyết việc tranh luận bằng một cuộc thi chạy đua. Chúng đồng ý lộ trình và bắt đầu cuộc đua.

Thỏ xuất phát nhanh như tên bắn và chạy thục mạng rất nhanh, khi thấy rằng mình đã khá xa Rùa, Thỏ nghĩ nên nghỉ cho đỡ mệt dưới một bóng cây xum xê lá bên vệ đường và nghỉ thư giãn trước khi tiếp tục cuộc đua.

Vì quá tự tin vào khả năng của mình, Thỏ ngồi dưới bóng cây và nhanh chóng ngủ thiếp đi trên đường đua. Rùa từ từ vượt qua Thỏ và sớm kết thúc đường đua.

Khi Thỏ thức dậy thì rùa đã đến đích và trở thành người chiến thắng. Thỏ giật mình tỉnh giấc và nhận ra rằng nó đã bị thua.

Không thể chấp nhận sự thật, Thỏ quyết định tái đấu. Lần này, thay vì dùng một trò thiên về sức lực, Thỏ quyết định thách đấu bằng cách đố Rùa một câu hỏi đầy hóc búa.

Cho đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh, không có khuyên và cạnh lặp.

Để tạo ra được một đồ thị có độ đẹp, ta cần điền các số nguyên dương ~c~ trên mỗi đỉnh (~c~ chỉ có thể là ~1~, ~2~, hoặc ~3~), sao cho với mỗi cạnh, tổng của hai số được điền trên ~2~ đỉnh được kết nối bởi cạnh đó là một số lẻ.

Thỏ đố Rùa có thể đếm số cách để điền các số ~1,2,3~ lên mỗi đỉnh sao cho tạo ra được một đồ thị đẹp. Do con số này có thể rất lớn, hãy in nó ra theo ~modulo~ ~998244353~.

Lưu ý: Rùa phải điền đúng một số trên mỗi đỉnh.

Để cho câu đố thêm phần học búa, Thỏ sẽ hỏi ~q~ câu có dạng như vậy.

Rùa dù là một sinh vật cute nhưng không giỏi đồ thị cho lắm, hãy giúp Rùa hoàn thành bài toán này nhé!

Input

• Dòng đầu tiên gồm số nguyên dương ~q~ miêu tả số câu hỏi.
• Đối với mỗi câu hỏi:
  • Dòng đầu tiên ~2~ số nguyên dương ~n,m~ miêu tả số đỉnh và cạnh của đồ thị.
  • ~m~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương ~u_i,v_i~ ~(1 \le u_i,v_i \le n, u_i \neq v_i)~ miêu tả cạnh thứ ~i~.

Output

• Với mỗi câu hỏi, in ra một dòng là số nguyên duy nhất là số cách điền thỏa mãn sau khi lấy phần dư cho ~998244353~.

Điều kiện

• ~1 \le q \le 3 \times 10^5~.
• ~1 \le n,m \le 3 \times 10^5~.
• Dữ liệu đảo bảo rằng tổng ~n~ trong tất cả các câu hỏi không vượt quá ~3 \times 10^5~, tương tự với tổng ~m~.

Subtask

• ~50\%~ số điểm: ~n \le 10, q \le 10~.
• ~30\%~ số điểm: Trong mọi câu hỏi, đồ thị có dạng cây.
• ~20\%~ số điểm: Không có ràng buộc gì thêm.

Ví dụ

Input:

2
7 7 
1 2
2 3
3 4
4 5
5 6
6 7
7 1
2 1
2 1

Output:

0
4

Giải thích:

Ở câu hỏi đầu tiên, không có cách điền nào thỏa mãn.

Ở câu hỏi thứ hai, có ~4~ cách điền như sau:

• Điền số ~1~ vào đỉnh ~1~, số ~2~ vào đỉnh ~2~.
• Điền số ~3~ vào đỉnh ~1~, số ~2~ vào đỉnh ~2~.
• Điền số ~2~ vào đỉnh ~1~, số ~1~ vào đỉnh ~2~.
• Điền số ~2~ vào đỉnh ~1~, số ~3~ vào đỉnh ~2~.

Alice vừa mới lạc vào một vùng đất rất kì lạ tên là "Bruhderland". Đây là một vùng đất lai giữa "Wonderland" và "Borderland", nơi có phép màu và cả những trò chơi sinh tử.

Bruhderland được biểu diễn bằng một ma trận ~n \times m~, với ô ~(i,j)~ là một trong các kí tự sau:

• .: có nghĩa là ô đất trống, có thể đi vào.
• *: có nghĩa là ô có một tảng đá, không thể đi vào.
• A: có nghĩa là có một trò chơi với độ khó ~A~ ở ô này, Alice rất giỏi nên sẽ có thể vượt qua trò chơi, nhưng sẽ mất ~1~ sức lực.
• B: có nghĩa là có một trò chơi với độ khó ~B~ ở ô này, Alice vẫn sẽ có thể vượt qua trò chơi, nhưng sẽ mất ~2~ sức lực.

Giả sử, Alice đang ở ô ~(i,j)~, cô có thể đi sang ~4~ ô kề cạnh nếu như ô đó không vượt qua ngoài bảng và không chứa tảng đá nào. Như đã nói, Bruhderland có cả yếu tố phép màu, vậy nên khi vào đây, cô đã học được cách đọc thần chú để phá hủy một tảng đá bất kì mà không mất sức lực nào (nghĩa là có thể đi vào ô chứa tảng đá vừa bị phá hủy), tuy nhiên do năng lực giới hạn, Alice chỉ có thể đọc thần chú ~k~ lần mà thôi.

Alice đang ở ô ~(1,1)~, để thoát ra khỏi Bruhderland, cô sẽ cần đến ô ~(n,m)~. Tuy nhiên, do khá lười tham gia vào các trò chơi, Alice muốn thoát ra khỏi Bruhderland sao cho tốn ít sức lực nhất.

Quan trọng: Dữ liệu đảm bảo kết quả không quá ~2500~.

Input: BRUHDERLAND.INP

• Dòng đầu tiên ghi ~3~ số nguyên dương ~n,m,k~ ~(1 \le n,m \le 1000, 0 \le k \le 5)~.
• ~n~ dòng sau, dòng thứ ~i~ gồm một xâu kí tự độ dài ~m~ miêu tả hàng thứ ~i~ của ma trận.
• Dữ liệu đảm bảo ô ~(1,1)~ là kí tự . và luôn tồn tại cách đi từ ~(1,1)~ tới ~(n,m)~ nếu sử dụng thần chú một cách hợp lý.

Output: BRUHDERLAND.OUT

• In ra một số nguyên dương là số sức lực ít nhất cần tiêu tốn để đến được ô ~(n,m)~.

Scoring:

• Subtask ~1~ ~(10\%)~: ~ n\times m \le 10^5~, ~k = 0~ và các ô khác ô ~(1,1)~ chỉ gồm kí tự A
• Subtask ~2~ ~(15\%)~: ~ n\times m \le 10^5~, ~k = 0~ và các ô khác ô ~(1,1)~ không có kí tự B và ..
• Subtask ~3~ ~(10\%)~: ~k = 0~ và các ô khác ô ~(1,1)~ không có kí tự B.
• Subtask ~4~ ~(10\%)~: Các ô khác ô ~(1,1)~ không có kí tự B.
• Subtask ~5~ ~(15\%)~: ~n \times m \le 10^5~ và ~k = 0~.
• Subtask ~6~ ~(20\%)~: ~n \times m \le 10^5~.
• Subtask ~7~ ~(20\%)~: Không có giới hạn gì thêm.

Sample Input 1

4 4 0
.AAA
AAAA
AAAA
AAAA

Sample Output 1

6

Sample Input 2

5 4 0
.AAA
***A
AAAA
A***
AAAA

Sample Output 2

13

Sample Input 3

5 4 0
.AAA
***B
AAAA
A**B
BAAA

Sample Output 3

9

Sample Input 4

5 4 2
.BAA
****
AABA
A***
BABA

Sample Output 4

6

Cho đồ thị vô hướng có trọng số gồm ~n~ đỉnh và ~m~ cạnh không chứa khuyên, mỗi cạnh có dạng ~(u,v,c)~, tức là cạnh nối hai đỉnh ~u~ và ~v~ có trọng số ~c~.

Với mỗi cạnh, hãy xác định xem cạnh đó có nằm trong mọi cây khung nhỏ nhất của đồ thị hay không.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, n-1 \le m \le 2*10^5)~
• ~m~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên ~u_i,v_i,w_i~ ~(1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9)~ - lần lượt là hai đỉnh và trọng số của cạnh thứ ~i~.
• Dữ liệu đảm bảo đồ thị liên thông.

Output:

• In ra ~m~ xâu kí tự, trong đó xâu thứ ~i~ là "Yes" nếu cạnh thứ ~i~ thuộc toàn bộ các cây khung nhỏ nhất của đồ thị, "No" nếu ngược lại.

Constraints:

• Có ~10\%~ số test ứng với ~m \le 20~
• Có ~20\%~ số test ứng với ~m \le 300~
• Có ~20\%~ số test ứng với ~m \le 4000~;
• Có ~20\%~ số test ứng với trọng số của mọi cạnh phân biệt.
• ~30\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input 1

5 7
4 3 2
1 2 2
1 4 7
2 5 1
1 3 9
2 4 9
2 3 7

Output 1

Yes Yes No Yes No No No 

Cho dãy ~a~ gồm ~n~ số nguyên dương. Bạn được chọn đúng ~k~ cặp số bằng các thao tác, mỗi thao tác có thể chọn một trong các cách sau:

• 1) Chọn ~2~ số đầu hàng.

• 2) Chọn ~2~ số cuối hàng.

• 3) Chọn ~1~ số đầu hàng và ~1~ số cuối hàng.

• 4) Loại ~1~ số đầu hàng ra khỏi hàng.

• 5) Loại ~1~ số cuối hàng ra khỏi hàng.

Sau mỗi thao tác, nếu bạn chọn thao tác ~1~, ~2~, ~3~ thì sẽ được cộng thêm số điểm bằng giá trị tuyệt đối của ~2~ số bạn chọn, đồng thời loại ~2~ số đó ra khỏi hàng và được tính là chọn 1 cặp số. Ngược lại với thao tác ~4~ và ~5~, bạn không được tính là chọn một cặp số.

Hãy tìm cách thực hiện đúng ~k~ thao tác để đem về số điểm là cao nhất. Biết ban đầu bạn có số điểm bằng 0.

Input

• Dòng đầu gồm ~2~ số nguyên dương ~n~ và ~k~ ~(2*k \le n)~
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~. ~(1 \le a_i \le 10^9)~

Ouput

• In ra một số nguyên duy nhất là số điểm lớn nhất có thể thu về sau khi thực hiện đúng ~k~ thao tác.

Subtask

• Có 40% test thỏa mãn điều kiện: ~n \le 300~, ~k \le 2~.
• Có 40% test thỏa mãn điều kiện: ~n \le 30, 2*k = n~.
• Có 20% test thỏa mãn điều kiện: ~n \le 300~

Sample Test

Input

6 2
1 3 10 2 1 4

Output

12

Giải thích:

• Thao tác ~1~: Chọn ~2~ thẻ cuối hàng và được cộng ~|4-1| = 3~ điểm.
• Thao tác ~2~: Loại thẻ ở cuối hàng có giá trị bằng ~2~.
• Thao tác ~3~: Chọn một thẻ ở đầu hàng và một thẻ ở cuối hàng, thu được thêm ~|10-1| = 9~ điểm.
• Tổng cộng sẽ được ~2~ cặp số tương ứng ~12~ điểm.