Bài tập

Cho hai xâu \(u\) và \(v\), mỗi xâu chỉ gồm các chữ số thập phân và biểu diễn một số nguyên không âm; các xâu có thể chứa các chữ số 0 vô nghĩa ở đầu (ví dụ 0089 biểu diễn số \(89\)).

Hãy so sánh giá trị của hai số và in ra số lớn hơn, viết dưới dạng chuẩn: đã bỏ hết các chữ số 0 vô nghĩa ở đầu (nếu giá trị bằng \(0\) thì in 0). Nếu hai số bằng nhau, in ra giá trị chung đó.

Gợi ý: viết hàm \(NORM(S)\) bỏ các chữ số 0 vô nghĩa và hàm \(COMP(u, v)\) so sánh hai số.

Input

• Dòng thứ nhất chứa xâu \(u\).
• Dòng thứ hai chứa xâu \(v\).

Output

• In ra số lớn hơn ở dạng chuẩn.

Constraints

• Mỗi xâu có độ dài từ \(1\) đến \(10^6\) và chỉ gồm các chữ số từ 0 đến 9.

Sample Input 1

0007
35

Sample Output 1

35

Sample Input 2

000480
0479

Sample Output 2

480

Một cửa hàng điện máy phát cho mỗi khách mua hàng một tấm phiếu ghi số may mắn. Các phiếu được ghi lại theo đúng thứ tự khách đến mua, và không có hai phiếu nào trùng số. Cuối đợt khuyến mãi, cửa hàng công bố một số trúng thưởng, chắc chắn là số có trên phiếu của một khách nào đó.

Hãy cho biết khách trúng thưởng là người thứ mấy (tính từ \(1\) theo thứ tự mua hàng).

Input

• Dòng đầu chứa số nguyên \(n\) là số khách hàng.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\), trong đó \(a_i\) là số may mắn của khách thứ \(i\).
• Dòng thứ ba chứa số nguyên \(k\) là số trúng thưởng.

Output

In ra một số nguyên là số thứ tự của khách hàng trúng thưởng.

Constraints

• \(1 \le n \le 4999\)
• \(1 \le a_i \le 5000\), các \(a_i\) đôi một khác nhau
• \(k\) bằng đúng một trong các số \(a_i\)

Sample Input

5
7 1 9 4 6
9

Sample Output

3

Explanation

Số \(9\) nằm ở vị trí thứ \(3\) trong dãy các phiếu.

Cho dãy gồm \(m\) số nguyên \(B_1, B_2, \ldots, B_m\). Hãy sắp xếp dãy thành dãy không giảm và in ra.

Gợi ý: có thể cài đặt sắp xếp nổi bọt (Bubble sort) và dùng một chương trình con \(Swap(a, b)\) để hoán đổi giá trị của hai phần tử; tuy nhiên chỉ cần in đúng kết quả.

Input

• Dòng đầu chứa số nguyên dương \(m\).
• Dòng thứ hai chứa \(m\) số nguyên \(B_1, B_2, \ldots, B_m\).

Output

• In ra dãy sau khi sắp xếp không giảm, các số cách nhau một dấu cách, trên một dòng.

Constraints

• \(1 \le m \le 10^3\)
• \(|B_i| \le 10^{18}\)

Sample Input 1

5
9 -2 7 7 0

Sample Output 1

-2 0 7 7 9

Trên con đường đến ngôi làng của một nàng công chúa có \(N\) chiếc rương vàng nằm nối tiếp nhau theo thứ tự đi qua. Rương thứ \(i\) chứa \(x_i\) đồng vàng. Tuy nhiên, những chiếc rương này bị yểm bùa: nếu bạn đã lấy vàng ở rương \(i-1\) thì rương \(i\) sẽ không mở ra được nữa. Nói cách khác, không được lấy hai rương liên tiếp.

Hãy tính tổng số đồng vàng lớn nhất có thể mang đi.

Input

• Dòng đầu tiên chứa số nguyên \(t\) là số bộ test.
• Mỗi bộ test gồm hai dòng: dòng đầu chứa số nguyên \(N\) là số rương; dòng tiếp theo chứa \(N\) số nguyên \(x_1, x_2, \dots, x_N\) (nếu \(N = 0\) thì dòng này để trống).

Output

Với mỗi bộ test, in ra một dòng là số vàng lớn nhất thu được.

Constraints

• \(1 \le t \le 10\)
• \(0 \le N \le 10^4\)
• \(0 \le x_i \le 10^4\)

Sample Input

3
6
4 1 1 9 1 3
0

4
5 5 5 5

Sample Output

16
0
10

Explanation

Bộ test đầu: lấy các rương 4, 9, 3 (vị trí 1, 4, 6) được \(16\). Bộ test thứ hai không có rương nào. Bộ test thứ ba: lấy hai rương cách nhau, được \(10\).