Cơm tấm contest round 1

Hào và An là đôi bạn thân. Một hôm Hào và An quyết định đo thử xem chân của ai dài hơn: chân của Hào dài \(A\) mét và chân của An dài \(B\) mét.

Yêu cầu

Bạn hãy đưa ra người có chân dài hơn.

Vì có nhiều cặp số cần so sánh, dữ liệu vào gồm nhiều testcase trong cùng một lần chạy chương trình.

Dữ liệu vào

Nhập từ bàn phím, gồm:

• Dòng 1: số nguyên \(T\) — số lượng testcase (\(1 \le T \le 10\)).
• \(T\) nhóm dòng tiếp theo, mỗi nhóm gồm 2 dòng mô tả một testcase:
• Dòng thứ nhất: số nguyên \(A\) (biểu diễn dưới dạng một chuỗi chữ số thập phân, không có chữ số 0 vô nghĩa ở đầu, không chứa dấu cách hay kí tự nào khác).
• Dòng thứ hai: số nguyên \(B\) (biểu diễn tương tự).

Ràng buộc: \(0 < A, B \le 10^{1000}\).

Dữ liệu ra

Với mỗi testcase, in ra một dòng chứa một kí tự duy nhất:

• H nếu chân Hào dài hơn (\(A > B\));
• A nếu chân An dài hơn (\(A < B\));
• = nếu chân hai người bằng nhau (\(A = B\)).

Kết quả của \(T\) testcase được in lần lượt theo đúng thứ tự xuất hiện trong dữ liệu vào, mỗi kết quả một dòng.

Ví dụ

Input

3
10
9
9
10
25
25

H
A
=

Giải thích:

• Testcase 1: \(A=10, B=9\). Vì \(10>9\) nên chân Hào dài hơn → H.
• Testcase 2: \(A=9, B=10\). Vì \(9<10\) nên chân An dài hơn → A.
• Testcase 3: \(A=25, B=25\). Hai người có chân bằng nhau → =.

Ràng buộc

Subtask 1 (40% số test tương ứng 40% số điểm): \(0 < A, B \le 10^{18}\) (đủ nhỏ để đọc trực tiếp bằng kiểu 64-bit có sẵn của ngôn ngữ lập trình), với mọi testcase trong file.
Subtask 2 (60% số test tương ứng 60% số điểm): \(0 < A, B \le 10^{1000}\) — không có ràng buộc gì thêm.

\(A\) và \(B\) luôn được cho dưới dạng chuẩn, không có chữ số 0 vô nghĩa ở đầu (ví dụ 007 sẽ không xuất hiện trong dữ liệu vào).

Lớp học nọ có \(n\) bạn nam lần lượt có chiều cao là \(a_1, a_2, \ldots, a_n\) và \(m\) bạn nữ có chiều cao lần lượt là \(b_1, b_2, \ldots, b_m\).

Yêu cầu

Với mỗi bạn nam, hãy cho biết chênh lệch chiều cao nhỏ nhất giữa bạn nam đó với một bạn nữ bất kì trong lớp.

Dữ liệu vào

Nhập từ bàn phím (standard input):

• Dòng đầu chứa hai số nguyên dương \(n, m\).
• Dòng thứ hai chứa \(n\) số nguyên dương lần lượt là chiều cao các bạn nam trong lớp.
• Dòng thứ ba chứa \(m\) số nguyên dương lần lượt là chiều cao các bạn nữ trong lớp.

Kết quả

In ra màn hình (standard output) \(n\) số lần lượt là chênh lệch chiều cao nhỏ nhất giữa bạn nam thứ \(i\) với một bạn nữ bất kì trong lớp.

Ràng buộc

• \(n, m, a_i, b_i \le 10^5\).

• Subtask 1 (50% số test tương ứng 50% số điểm): \(n, m \le 10^3\).

• Subtask 2 (20% số test tương ứng 20% số điểm): Các bạn nam trong lớp có chiều cao giống hệt nhau.
• Subtask 3 (30% số test tương ứng 30% số điểm): \(n, m \le 10^5\).

Ví dụ

Input

4 5
130 140 150 160
125 136 169 190 110

Output

5 4 14 9

Quốc Dũng có một dãy \(a\) gồm \(n\) phần tử, các phần tử được đánh số từ 1 đến \(n\). Trong lớp của Quốc Dũng có Minh Hiếu và Phúc Hiếu là đôi bạn cùng lớp 10I. Minh Hiếu và Phúc Hiếu mỗi người chọn một chỉ số (hai chỉ số này không nhất thiết phải khác nhau), làm cho các phần tử có chỉ số nằm giữa hai chỉ số mà Minh Hiếu và Phúc Hiếu chọn (tính cả hai đầu mút) đều được nhân lên \(X\) lần.

Ví dụ dãy \(a = [5, 3, 7, 1]\), \(X = 2\): nếu Minh Hiếu chọn chỉ số 3, Phúc Hiếu chọn chỉ số 2 thì các phần tử ở chỉ số 2 và 3 được nhân đôi, dãy biến thành \([5, 6, 14, 1]\).

Yêu cầu

Hãy đưa ra tổng các phần tử của mảng nhỏ nhất có thể sau khi hai bạn chọn 2 chỉ số bất kì (không nhất thiết khác nhau) rồi thực hiện phép nhân lên mảng như trên.

Dữ liệu vào

Nhập từ bàn phím (standard input), gồm 2 dòng:

• Dòng 1: hai số nguyên \(n\) và \(X\) cách nhau bởi một khoảng trắng.
• Dòng 2: \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) cách nhau bởi khoảng trắng.

Dữ liệu ra

In ra màn hình (standard output) một số nguyên duy nhất là tổng nhỏ nhất có thể của mảng sau khi thực hiện phép nhân.

Ràng buộc

• \(1 \le n \le 10^6\).
• \(-10^9 \le a_i \le 10^9\).

• \(-1000 \le X \le 1000\).

• Subtask 1 (30% số test tương ứng 30% số điểm): \(n \le 10^2\).

• Subtask 2 (40% số test tương ứng 40% số điểm): \(n \le 10^3\).
• Subtask 3 (30% số test tương ứng 30% số điểm): \(n \le 10^6\).

Ví dụ

Input 1

4 2
5 3 7 1

17

Input 2

3 0
-1 -2 -3

-5

Paolo có \(n\) thẻ bài xếp thành một hàng ngang, đánh số từ trái sang phải từ 1 đến \(n\). Mỗi thẻ bài có hai mặt: một mặt ghi số nguyên dương \(a_i\), mặt còn lại ghi số nguyên dương \(b_i\). Ban đầu, tất cả thẻ bài được đặt sao cho mặt ghi \(a_i\) ngửa lên, mặt ghi \(b_i\) úp xuống.

Trong một lượt chơi, Paolo chọn một số nguyên dương \(T\) rồi lật tất cả những thẻ bài có số ghi ở mặt đang ngửa (hiện tại) nhỏ hơn hoặc bằng \(T\).

Paolo chơi \(k\) lượt: ở lượt thứ \(i\), Paolo chọn số nguyên dương \(T_i\).

Sau khi chơi đủ \(k\) lượt, hãy tính tổng \(n\) số ghi trên mặt đang ngửa của các thẻ bài.

Dữ liệu vào

Nhập từ bàn phím (standard input):

• Dòng đầu tiên gồm hai số nguyên dương \(n, k\) (\(1 \le n, k \le 2 \times 10^5\)).
• \(n\) dòng sau, dòng thứ \(i\) chứa hai số nguyên dương \(a_i, b_i\) (\(1 \le a_i, b_i \le 10^9\)) là hai số ghi trên thẻ bài thứ \(i\). Ban đầu mặt \(a_i\) ngửa lên, mặt \(b_i\) úp xuống.
• \(k\) dòng sau, dòng thứ \(i\) gồm một số nguyên dương \(T_i\) (\(1 \le T_i \le 10^9\)) là giá trị Paolo chọn ở lượt thứ \(i\).

Kết quả

In ra màn hình (standard output) một số nguyên dương duy nhất là tổng \(n\) số ghi trên mặt ngửa của \(n\) thẻ bài.

Ràng buộc

• Subtask 1 (20% số test, tương ứng 20% số điểm): \(n, k \le 5000\).
• Subtask 2 (25% số test, tương ứng 25% số điểm): \(k \le 2 \times 10^4\) và dãy \(T_1, T_2, \ldots, T_k\) gồm không quá 100 giá trị phân biệt.
• Subtask 3 (25% số test, tương ứng 25% số điểm): \(T_1 \le T_2 \le \cdots \le T_k\).
• Subtask 4 (30% số test, tương ứng 30% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

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

Output

25

Giải thích: Ban đầu, các thẻ bài được xếp như sau (mặt ngửa/mặt úp): \(\dfrac{2}{10}, \dfrac{1}{9}, \dfrac{3}{8}, \dfrac{7}{7}, \dfrac{4}{6}\).

• Lượt 1 (\(T=8\)): mọi mặt ngửa hiện tại \(2, 1, 3, 7, 4\) đều \(\le 8\) nên cả 5 thẻ đều được lật. Các mặt ngửa lần lượt là \(10, 9, 8, 7, 6\).
• Lượt 2 (\(T=2\)): không có mặt ngửa nào \(\le 2\) nên không thẻ nào được lật.
• Lượt 3 (\(T=9\)): các thẻ 2, 3, 4, 5 có mặt ngửa là \(9, 8, 7, 6\) đều \(\le 9\) nên được lật. Thẻ 1 có mặt ngửa là \(10 > 9\) nên giữ nguyên. Các mặt ngửa lúc này lần lượt là \(10, 1, 3, 7, 4\).

Tổng: \(10 + 1 + 3 + 7 + 4 = 25\).