Cho một phân số thập phân hữu hạn gồm ~n~ chữ số sau dấu thập phân. Hãy tìm hai số tự nhiên ~a~ và ~b~ sao cho ~a / b~ bằng đúng phân số thập phân đó.

Chính thức hơn: phân số thập phân có dạng ~0.d_1 d_2 \ldots d_n~, trong đó ~d_n \ne 0~.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 17~).

Dòng thứ hai chứa ~n~ chữ số liên tiếp sau dấu thập phân. Đảm bảo chữ số cuối cùng khác ~0~.

Dữ liệu ra

Nếu không tồn tại cặp ~(a, b)~ thỏa mãn, in ra NO.

Ngược lại, in ra YES, sau đó in hai số tự nhiên ~a~ và ~b~ sao cho ~a / b~ bằng đúng phân số thập phân đã cho và ~0 < a < b < 10^6~. Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Ví dụ

Ghi chú

Với ví dụ đầu tiên: ~1 / 5 = 0.2~.

Với ví dụ thứ hai: ~69 / 100 = 0.69~.

Với ví dụ thứ ba: ~1 / 1000 = 0.001~.

Cho một tam giác vuông có độ dài cạnh huyền là ~c~ và độ dài đường cao hạ xuống cạnh huyền là ~h~. Tính diện tích tam giác đó, hoặc cho biết tam giác như vậy không tồn tại.

Dữ liệu vào

Dòng thứ nhất chứa một số nguyên ~c~ (~1 \le c \le 10^4~) — độ dài cạnh huyền.

Dòng thứ hai chứa một số nguyên ~h~ (~1 \le h \le 10^4~) — độ dài đường cao hạ xuống cạnh huyền.

Dữ liệu ra

In ra diện tích của tam giác. Nếu tam giác không tồn tại, in ra ~-1~.

Ví dụ

Xét thuật toán phân chia ~n~ quả cam vào hai đống A và B theo các bước như sau:

• Bước 1: đặt 1 quả vào đống A, sau đó đặt 1 quả vào đống B;
• Bước 2: đặt 2 quả vào đống A, sau đó đặt 1 quả vào đống B;
• Bước 3: đặt 3 quả vào đống A, sau đó đặt 1 quả vào đống B;
• Bước ~i~: đặt ~i~ quả vào đống A, sau đó đặt 1 quả vào đống B; ...

Số ~n~ được gọi là số Cheburashka nếu ~n~ quả cam có thể được phân chia hoàn toàn bằng thuật toán trên (tức là sau một số bước nguyên dương, vừa hết đúng ~n~ quả), đồng thời quả cam cuối cùng được đặt vào đống B.

Cho số nguyên ~k~, hãy tìm số Cheburashka thứ ~k~ theo thứ tự tăng dần.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên ~k~ (~1 \le k \le 10^9~).

Dữ liệu ra

In ra số Cheburashka thứ ~k~.

Ví dụ

Cho một tờ giấy kẻ ô kích thước ~n \times m~ ô vuông và một số nguyên ~s~. Một máy cắt laser hoạt động theo quy trình sau:

1. Đưa tờ giấy vào máy.
2. Máy thực hiện ~x~ nhát cắt thẳng đứng dọc theo các đường kẻ ô.
3. Máy thực hiện ~y~ nhát cắt nằm ngang dọc theo các đường kẻ ô.
4. Kết quả thu được ~(x+1)(y+1)~ tờ giấy mới.

Hãy tìm số nhát cắt tối thiểu ~x + y~ cần thực hiện, sao cho từ các tờ giấy thu được có thể chọn ra một tập con có tổng diện tích đúng bằng ~s~ ô vuông.

Dữ liệu vào

Một dòng duy nhất chứa ba số nguyên ~n~, ~m~ và ~s~ (~1 \le n, m \le 10^5~, ~1 \le s \le n \cdot m~).

Dữ liệu ra

In ra một số nguyên — số nhát cắt tối thiểu cần thực hiện.

Ví dụ

Ghi chú

Với ví dụ thứ ba, ~s = n \cdot m~ nên không cần cắt.

Trên mặt phẳng tọa độ có ~n \times n~ điểm sáng được đặt tại tất cả các điểm nguyên ~(i, j)~ với ~0 \le i, j \le n-1~. Các điểm liền kề theo hàng hoặc cột cách nhau một đơn vị.

Một robot cần di chuyển theo một đường gấp khúc để đi qua tất cả ~n^2~ điểm sáng. Robot có thể bắt đầu tại bất kỳ điểm nguyên nào có tọa độ trong đoạn ~[-1000, 1000]~. Robot chỉ di chuyển theo đường thẳng, do đó quỹ đạo của nó là một đường gấp khúc.

Hãy xây dựng một hành trình cho robot thỏa mãn tất cả các điều kiện sau:

• Đường gấp khúc gồm đúng ~2n - 2~ đoạn thẳng.
• Điểm đầu, điểm cuối và tất cả các điểm ngoặt đều có tọa độ nguyên trong đoạn ~[-1000, 1000]~.
• Mọi điểm sáng đều nằm trên đường gấp khúc.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên ~n~ (~3 \le n \le 100~).

Dữ liệu ra

In ra ~2n - 1~ dòng, mỗi dòng gồm hai số nguyên — tọa độ của một điểm trên hành trình. Dòng đầu tiên là tọa độ điểm xuất phát, ~2n - 3~ dòng tiếp theo là tọa độ các điểm ngoặt theo thứ tự, dòng cuối cùng là tọa độ điểm kết thúc.

Nếu tồn tại nhiều đáp án hợp lệ, in ra bất kỳ đáp án nào.

Ví dụ

Ghi chú

Với ~n = 3~, robot xuất phát tại ~(2, 2)~ và kết thúc tại ~(0, 1)~. Hành trình gồm 4 đoạn thẳng đi qua toàn bộ 9 điểm sáng.

Cho đồ thị ~n~ đỉnh, ban đầu không có cạnh nào. Thực hiện ~q~ truy vấn, mỗi truy vấn thuộc một trong hai loại:

• + v u c — thêm cạnh ~(v, u)~ có màu ~c~. Đảm bảo trước đó chưa tồn tại cạnh màu ~c~ giữa ~v~ và ~u~.
• - v u c — xóa cạnh ~(v, u)~ có màu ~c~. Đảm bảo cạnh đó đang tồn tại.

Màu ~c~ được gọi là màu xuất sắc nếu mỗi đỉnh kề với nhiều nhất một cạnh màu ~c~. Độ đẹp của màu ~c~ được định nghĩa là số cạnh có màu ~c~ trong đồ thị.

Sau mỗi truy vấn, hãy in ra tổng độ đẹp của tất cả các màu xuất sắc.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~2 \le n \le 10^5~, ~1 \le q \le 10^5~).

Mỗi dòng trong ~q~ dòng tiếp theo mô tả một truy vấn (~1 \le v, u \le n~, ~v \ne u~, ~1 \le c \le 10^5~).

Dữ liệu ra

Sau mỗi truy vấn, in ra một số nguyên — tổng độ đẹp của tất cả các màu xuất sắc.

Ví dụ

Ghi chú

Trong ví dụ đầu tiên:

• Sau truy vấn 1: màu 1 xuất sắc (1 cạnh). Tổng = 1.
• Sau truy vấn 2: màu 1 và màu 2 đều xuất sắc. Tổng = 1 + 1 = 2.
• Sau truy vấn 3: đỉnh 2 kề với hai cạnh màu 1, nên màu 1 không còn xuất sắc. Chỉ màu 2 xuất sắc. Tổng = 1.
• Sau truy vấn 4: xóa cạnh ~(2, 1)~ màu 1, màu 1 trở lại xuất sắc. Tổng = 1 + 1 = 2.
• Sau truy vấn 5: thêm cạnh ~(2, 4)~ màu 4. Cả ba màu đều xuất sắc. Tổng = 1 + 1 + 1 = 3.

Có ~n~ lá bài hai mặt. Lá bài thứ ~i~ có giá trị ~a_i~ ở mặt trước và ~b_i~ ở mặt sau. Các lá bài được xếp thành một hàng từ trái sang phải.

Cho phép thực hiện hai loại thao tác tùy ý số lần:

• Lật một lá bài bất kỳ: hoán đổi mặt trước và mặt sau của lá đó.
• Đổi chỗ hai lá bài bất kỳ mà không lật.

Mục tiêu: sắp xếp các lá bài sao cho dãy giá trị mặt trước từ trái sang phải không giảm, đồng thời dãy giá trị mặt sau từ trái sang phải cũng không giảm.

Hãy xác định xem mục tiêu có đạt được không, và nếu có thì in ra cách sắp xếp.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^5~).

Dòng thứ hai chứa ~n~ số nguyên ~a_i~ (~1 \le a_i \le 10^9~) — giá trị mặt trước của các lá bài theo thứ tự ban đầu.

Dòng thứ ba chứa ~n~ số nguyên ~b_i~ (~1 \le b_i \le 10^9~) — giá trị mặt sau của các lá bài theo thứ tự ban đầu.

Dữ liệu ra

Nếu không thể đạt được mục tiêu, in ra ~-1~.

Ngược lại, in ra hai dòng: dòng đầu gồm ~n~ số nguyên là dãy giá trị mặt trước sau khi sắp xếp, dòng hai gồm ~n~ số nguyên là dãy giá trị mặt sau sau khi sắp xếp.

Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Ví dụ

Ghi chú

Với ví dụ đầu tiên, một cách sắp xếp hợp lệ là: lật lá 1, lật lá 2, sau đó đổi chỗ để thu được thứ tự ~(1|5),\ (2|6),\ (3|7),\ (4|8)~, trong đó ~x|y~ biểu thị lá có mặt trước ~x~ và mặt sau ~y~.

Cho ba điểm phân biệt ~(x_1, y_1)~, ~(x_2, y_2)~, ~(x_3, y_3)~ trên mặt phẳng. Hãy tìm một đường thẳng sao cho tổng khoảng cách từ ba điểm đến đường thẳng đó là nhỏ nhất.

Dữ liệu vào

Một dòng duy nhất chứa sáu số nguyên ~x_1,\ y_1,\ x_2,\ y_2,\ x_3,\ y_3~ — tọa độ của ba điểm (~-10^9 \le x_1, y_1, x_2, y_2, x_3, y_3 \le 10^9~). Đảm bảo ba điểm đôi một phân biệt.

Dữ liệu ra

In ra tọa độ nguyên của hai điểm phân biệt nằm trên đường thẳng tối ưu. Tọa độ của các điểm in ra không được vượt quá ~10^9~ về giá trị tuyệt đối.

Ví dụ