Trên mặt phẳng tọa độ hai chiều ~Oxy~ cho ~n~ điểm, các điểm có tọa độ ~(x_1,y_1), (x_2,y_2), ..., (x_n, y_n)~. Độ dốc hay hệ số góc của đường thẳng nối 2 điểm là ~\frac{y_i-y_j}{x_i-x_j}~ được miêu tả như hình sau:

YouAreMyGalaxy muốn chọn ra ít nhất ~k~ điểm từ tập ~n~ điểm sao cho độ dốc tối đa của đường nối hai điểm trong tập ~k~ điểm đã chọn là nhỏ nhất có thể.

Yêu cầu: Hãy tìm ra độ dốc tối đa được tìm thấy từ tập điểm được chọn.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n, k~ (~k\le n \le 10^5~) là số điểm trên mặt phẳng và số điểm ít nhất cần chọn.

~n~ dòng tiếp, mỗi dòng chứa hai số nguyên ~x_i, y_i~ (~0\le x_i, y_i \le 10^9~) mô tả một điểm trong tập.

Dữ liệu đảm bảo không có hai điểm nào có cùng hoành độ.

Output

In ra một số thực làm tròn đến 6 chữ số sau phần thập phân là hệ số góc lớn nhất trong tập điểm tìm được.

Scoring

Có ~30\%~ số điểm của bài với ~n\le 20~

Có ~40\%~ số điểm của bài với ~n\le 2000~

Còn lại không có điều kiện gì thêm

Sample Input 1

4 3
1 2
2 4
3 3
4 1

Sample Output 1

-1.000000

Sample Input 2

2 2
1 1
5 3

Sample Output 2

0.500000

Cho số nguyên dương ~N~, một xúc xắc đều ~M~ mặt được đánh số từ ~1~ đến ~M~ và một dãy ~A~ độ dài ~M~.

Bạn có một số nguyên ~X~. Ban đầu ~X~ bằng ~1~.

Bạn sẽ lăn xúc xắc liên tục nếu ~X~ còn nhỏ hơn ~N~. Nếu lăn xúc xắc ra mặt có đánh số là ~k~, ~X~ sẽ có giá trị mới bằng ~X×A_k~.

Yêu cầu: Đếm số cách để số ~X~ bằng ~N~ sau khi lăn xong theo mod ~998244353~.

Input

Dòng thứ nhất gồm ~2~ số nguyên dương ~N, M~ (~N \le 10^{18},~ ~M \le 100~)

Dòng thứ hai gồm ~M~ số nguyên biểu diễn mảng ~A~ (~2 \le A_i\le 10^6~)

Output

In ra kết quả là một số nguyên không âm là kết quả bài toán, vì đáp án có thể rất lớn nên hãy in ra số dư khi chia cho ~998244353~.

Scoring

Gọi ~K~ là phần tử lớn nhất trong dãy ~A~.

Có ~10\%~ số điểm với ~N \le 10^6,~ ~M \le 6~.

Có ~20\%~ số điểm khác với ~N \le 10^{18},~ ~M \le 6~.

Có ~30\%~ số điểm khác với ~N \le 10^{18},~ ~K \le 12~.

Còn lại không có điều kiện gì thêm.

Sample Input 1

12 11
2 3 4 5 6 7 8 9 10 11 12

Sample Output 1

8

Sample Input 2

2 2
2 2

Sample Output 2

2

Sample Input 3

123456 6
2 3 4 5 6 643

Sample Output 3

688

Hợp rồi lại tan, tan rồi lại hợp, có khi chưa kịp hợp mà đã tan từ lúc nào không hay. Cho dãy ~a~ là một hoán vị của dãy ~\{1,2,...,n\}~, một đoạn con liên tiếp gồm các phần tử ~a_l, a_{l+1},...,a_r~ được kí hiệu là ~a[l..r]~.

Lần lượt thực hiện ~q~ thao tác, mỗi thao tác thuộc một trong hai dạng:

• 1 ~p~: in ra ~a_p~

• 2 ~p~: thực hiện ~a:=Merge(a[1..p], a[p+1..n])~

Hàm merge sử dụng bên trên được mô tả dưới đây:

func Merge(dãy a, dãy b):
     khởi tạo dãy c rỗng
     while (a và b không rỗng)
          if (a[0] > b[0])
               thêm b[0] vào cuối c
               xoá b[0] khỏi b
          else
               thêm a[0] vào cuối c
               xoá a[0] khỏi a
     while (a không rỗng)
          thêm a[0] vào cuối c
          xoá a[0] khỏi a
     while (b không rỗng)
          thêm b[0] vào cuối c
          xoá b[0] khỏi b
     return c

Yêu cầu: Với mỗi thao tác loại 1, hãy in ra giá trị của phần tử tương ứng trong truy vấn.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n, q~ (~1\le n,q \le 2\times 10^5~) là số phần tử của dãy và số truy vấn.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,...,a_n~ (~a_i\le n, a_i \neq a_j~ với ~i\neq j~).

~q~ dòng tiếp, mỗi dòng nhập vào hai số nguyên ~v, p~ (~v\in \{1, 2\}, 1\le p \le n~) mô tả một thao tác.

Output

In ra trên nhiều dòng, mỗi dòng in ra một số là đáp án cho thao tác loại 1 tương ứng trong đầu vào

Scoring

Có ~50\%~ số điểm của bài ứng với ~n,q \le 5000~

Còn lại không có điều kiện gì thêm

Sample Input 1

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

Sample Output 1

4
1
2

Lưu ý: Đây là bài tập interactive, các bạn hãy xem hướng dẫn cách làm dạng bài này tại đây

Khuôn viên trường Đại học Sư Phạm vô cùng rộng lớn, có thể coi như là một mặt phẳng tọa độ hai chiều ~Oxy~. Trong Đại học Sư Phạm Hà Nội có một trường cấp ba chuyên không cổng, được ví như một tòa thành vững chắc, biểu diễn bởi một đa giác không tự cắt có các cạnh song song với một trong hai trục tọa độ.

Dưới đây là một ví dụ về tòa thành Chuyên Sư phạm:

Một robot xe tự hành được đưa vào sử dụng để giám sát an ninh của tòa thành; robot xe tự hành này chỉ có thể đi dọc theo tường thành, trên đường biên theo một hướng nhất định đã được lập trình từ trước. Robot xe tự hành này được lắp đặt cảm biến để khi tới một ngã rẽ, robot sẽ tự rẽ so cho vẫn di chuyển dọc theo tường thành và không đi ra ngoài.

Hôm nay, Giáo sư X, người cài đặt robot xe tự hành đã đi vắng nên không ai biết chiếc xe đang nằm ở trên vị trí nào cũng như có thể di chuyển theo hướng nào; little_aurora được giao nhiệm vụ xác định vị trí của chiếc xe. Tất nhiên little_aurora không thể nhìn thấy robot, anh chỉ có thể ra lệnh cho chiếc xe di chuyển và nhận thông tin được robot gửi về.

Cụ thể hơn, little_aurora có thể yêu cầu chiếc xe thực hiện di chuyển ~k~ đơn vị độ dài theo đường biên của tường thành, sau khi robot di chuyển tới nơi, nó sẽ gửi về cho anh thông tin về số lần xe rẽ trái và số lần xe rẽ phải. little_aurora được thực hiện thao tác trên không quá ~5000~ lần, dựa vào thông tin nhận được sau khi thực hiện các truy vấn, anh cần dưa ra tọa độ của robot tại thời điểm trả lời.

Yêu cầu: Sau bài tập gym màng nhĩ hôm qua, bây giờ little_aurora đang rất mệt mỏi và đau đớn, anh không thể hoàn thành nhiệm vụ được. Bạn hãy giúp little_aurora giải quyết vấn đề này nhé.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~n\le 2000~) là số đỉnh của đa giác biểu diễn tường thành.

~n~ dòng tiếp, mỗi dòng chứa hai số nguyên ~x_i, y_i~ (~x_i,y_i\le 10^5~) mô tả tọa độ các đỉnh của tường thành theo đúng thứ tự.

Dữ liệu đảm bảo vị trí của robot là duy nhất, tức là không bao giờ có hai điểm khác nhau trên tòa thành mà cho cùng một kết quả với mọi giá trị ~k~ của thao tác truy vấn.

Tiếp theo, bạn sẽ thực hiện các thao tác truy vấn để tìm vị trí của robot.

Interaction

Để đưa ra một truy vấn, hãy in ra theo một trong hai dạng sau:

• + k: Yêu cầu robot xe tự hành đi thêm ~k~ đơn vị độ dài (~1\le k\le 10^9~), sau đó trình chấm sẽ trả về hai số là số lần rẽ trái và số lần rẽ phải của xe.

• ! x y: Trả lời vị trí của robot là ở điểm ~(x, y)~.

Nếu robot kết thúc lệnh di chuyển tại một đỉnh, nó sẽ rẽ theo hướng của đường đi trước khi kết thúc lệnh di chuyển, vì vậy lệnh di chuyển tiếp theo sẽ bắt đầu bằng việc đi thẳng.

Scoring

Có ~30\%~ số điểm của bài với ~n\le 100~ và ~x_i, y_i\le 50~.

Có ~30\%~ số điểm khác của bài với ~n\le 100~.

Còn lại không có điều kiện gì thêm.

Sample Input 1

8
2 4
6 4
6 2
4 2
4 3
3 3
3 2
2 2

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

Sample Output 1

+ 14
+ 2
+ 12
+ 1
+ 13
+ 1
+ 1
+ 13
! 4 3

Notes

Trong test ví dụ, ban đầu robot nằm ở vị trí ~(3,3)~ và di chuyển ngược hướng với thứ tự nhập vào.

Đất nước Chuyên Sư phạm là một đất nước rộng lớn và phồn vinh với ~n~ trung tâm kinh tế lớn; để thuận tiện, các trung tâm kinh tế được đánh số từ ~1~ đến ~n~. Trước đây, vì để phát triển kinh tế, nhà nước đã xây dựng các con đường cao tốc (hai chiều) nối giữa các trung tâm kinh tế. Cụ thể hơn, giữa hai trung tâm kinh tế bất kỳ đều có một con đường, con đường nối giữa hai trung tâm kinh tế ~u~ và ~v~ có độ dài là ~w~ km.

Vì quy hoạch trong quá khứ không hợp lí, việc trung chuyển hàng hóa từ một trung tâm kinh tế tới một trung tâm kinh tế khác có thể không đi qua cao tốc nối trực tiếp chúng mà đi vòng qua một số cao tốc khác nhằm giảm thiểu thời gian. Khi đi qua nhiều cao tốc, quãng đường phải di chuyển là tổng độ dài các cao tốc đi qua. Trong ví dụ dưới đây, nếu vận chuyển hàng hóa theo tuyến đường ~5\rightarrow 4\rightarrow 2\rightarrow 3~ thì quãng đường là ~8~, còn theo tuyến đường ~5\rightarrow 1\rightarrow 4\rightarrow 2\rightarrow 3~ thì quãng đường là ~12~.

Đảng và nhà nước Chuyên Sư phạm đã quyết định tiến lên một bước lớn trên con đường quá độ lên chủ nghĩa xã hội: Tách biệt kinh tế nhà nước và kinh tế ngoài nhà nước. Để làm được như vậy, nhà nước cần chia các trung tâm kinh tế ra làm hai nhóm là trung tâm kinh tế nhà nước và trung tâm kinh tế ngoài nhà nước, mỗi thành phần kinh tế chỉ hoạt động tại các trung tâm kinh tế thuộc nhóm tương ứng.

Quãng đường trung chuyển hàng hóa của một nhóm kinh tế được định nghĩa là quãng đường trung chuyển hàng hóa lớn nhất giữa hai trung tâm thuộc nhóm đó. Nhà nước cần phân nhóm các trung tâm kinh tế sao cho tổng quãng đường trung chuyển hàng hóa của hai nhóm thành phần kinh tế là bé nhất có thể. Nói cách khác, nếu gọi ~A~ là quãng đường trung chuyển hàng hóa của nhóm kinh tế nhà nước, ~B~ là quãng đường trung chuyển hàng hóa của nhóm kinh tế ngoài nhà nước, ta cần cực tiểu hóa ~A+B~.

Yêu cầu: Bạn hãy giúp Đảng và nhà nước Chuyên Sư phạm tìm cách phân nhóm tốt nhất nhé.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~n\le 400~) là số trung tâm kinh tế trong đất nước Chuyên Sư phạm.

~n-1~ dòng tiếp, dòng thứ ~i~ chứa các số nguyên ~d_{i,i+1}, d_{i,i+2},..., d_{i,n}~ (~0\le d_{i,j}\le 10^9~), trong đó ~d_{i,j}~ là độ dài con đường nối giữa hai trung tâm kinh tế ~i~ và ~j~.

Output

In ra một số nguyên duy nhất là tổng quãng đường trung chuyển hàng hóa trong phương án tìm được.

Scoring

Có ~20\%~ số điểm của bài với ~n\le 20~

Có ~30\%~ số điểm khác với ~n\le 40~

Có ~20\%~ số điểm khác với ~n\le 200~

Còn lại không có điều kiện gì thêm

Sample Input 1

5
2 5 7 6
9 8 4
2 6
4

Sample Output 1

7

Notes

Trong test ví dụ, ta chia các trung tâm kinh tế thành 2 nhóm: ~\{2\}~ và ~\{1, 3, 4, 5\}~. Khi đó tổng quãng đường trung chuyển của nhóm đầu tiên là ~0~ và quãng đường trung chuyển của nhóm thứ hai là ~7~, tổng là ~7~.