Cho một số nguyên dương ~a~.
Hãy in ra tam giác sao gồm các ký tự * sao cho:

• Hàng đầu tiên có ~a~ dấu *;
• Hàng thứ hai có ~a - 1~ dấu *;
• ...
• Hàng cuối cùng có 1 dấu *.

Mỗi hàng được in trên một dòng riêng, không có ký tự thừa ở đầu hoặc cuối dòng.

Input

Gồm một dòng duy nhất chứa số nguyên ~a~.
~(1 ≤ a ≤ 1000)~

Output

In ra ~a~ dòng, trong đó dòng thứ ~i~ ~(1 ≤ i ≤ a)~ chứa đúng ~a - i + 1~ ký tự *.
Mỗi dòng kết thúc bằng ký tự xuống dòng.

Sample Test

Input:

5

Output:

*****
****
***
**
*

Input:

1

Output:

*

Cho ba số tự nhiên ~A, B, K~ (~1 \le A, B \le 10^9, 1 \le K \le 15~).

Yêu cầu: Hãy tìm số tự nhiên ~C~ nhỏ nhất sao cho tích của ba số ~A, B, C~ có ít nhất ~K~ chữ số ~0~ tận cùng.

Dữ liệu: Nhập vào ba số tự nhiên lần lượt theo thứ tự là ~A, B~ và ~K~. Mỗi số viết trên một dòng.

Kết quả: Đưa ra một số duy nhất là số tự nhiên ~C~ thỏa mãn yêu cầu đề bài.

Ví dụ:

Chấm điểm:

• Nếu chương trình chạy đúng những trường hợp ~1 \le A, B \le 10^3, 1 \le K \le 9~, thí sinh sẽ được ~40~ điểm;
• Nếu chương trình chạy đúng những trường hợp ~1 \le A, B \le 10^9, 1 \le K \le 15~ thí sinh sẽ được ~100~ điểm.

Cho một số nguyên dương ~n~.
Xét giai thừa của ~n~, ký hiệu là ~n! = 1 × 2 × 3 × … × n~.

Yêu cầu: Đếm số lượng chữ số ~0~ liên tiếp ở cuối biểu diễn thập phân của ~n!~.

Input

Gồm một dòng duy nhất chứa số nguyên ~n~.
~(1 ≤ n ≤ 10^6)~

Output

In ra một số nguyên duy nhất — là số lượng chữ số ~0~ tận cùng của ~n!~.

Sample Test

Input:

10

Output:

2

Input:

5

Output:

1

Một người nông dân nọ có một mảnh đất có dạng hình tứ giác lồi. Mảnh đất đó được trải trên mặt phẳng toạ độ ~Oxy~ với bốn đỉnh có toạ độ tương ứng theo chiều kim đồng hồ là ~A(x_1, y_1)~, ~B(x_2, y_2)~, ~C(x_3, y_3)~ và ~D(x_4, y_4)~. Bác nông dân cần biết diện tích của mảnh đất để tính toán lợi nhuận nhưng bác còn vướng bận công việc cày cấy. Bạn hãy giúp bác nông dân nhé!

Input

Gồm bốn dòng, dòng thứ ~i~ chứa hai số nguyên ~x_i~ và ~y_i~ (~|x_i|, |y_i| \leq 100~).

Output

In ra diện tích của mảnh đất tứ giác. Kết quả được coi là đúng với sai số không vượt quá ~10^{-3}~.

Sample Test 1

Input:

3 3 
6 3
4 1
1 1

Output:

6

Explanation: Mảnh đất tứ giác lồi hiện tại có dạng một hình bình hành. Dễ dàng tính được diện tích của hình bình hành này là 6 (đơn vị).

Sample Test 2

Input:

0 0
1 5
5 4
5 0

Output:

20.499999999999996

Cho một số nguyên dương ~n~.
Hãy đếm số bộ gồm bốn số nguyên dương ~(x₁, x₂, x₃, x₄)~ thỏa mãn:

• ~x₁ < x₂ < x₃ < x₄~.
• ~x₁ + x₂ + x₃ + x₄ = n~.

Input

Gồm một dòng duy nhất chứa số nguyên dương ~n~.
~(1 ≤ n ≤ 50)~

Output

In ra một số nguyên là số lượng bộ ~(x₁, x₂, x₃, x₄)~ thỏa mãn điều kiện đã cho.

Sample Test

Input:

10

Output:

1

Input:

15

Output:

6

Cho một ma trận có kích thước ~n × m~, hãy in ra toàn bộ phần tử của ma trận theo đường chéo zigzag.
Cụ thể: bắt đầu từ phần tử ở góc trên bên trái ~(1,1)~, di chuyển theo các đường chéo luân phiên hướng lên-phải và xuống-trái, cho đến khi in hết các phần tử và kết thúc tại ~(n,m)~.

Input

Gồm:

• Dòng đầu tiên chứa hai số nguyên ~n~, ~m~.
  ~(1 ≤ n, m ≤ 1000)~
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên ~Aᵢⱼ~ ~(1 ≤ Aᵢⱼ ≤ 100)~, biểu diễn các phần tử của ma trận.

Output

In ra dãy gồm ~n × m~ số nguyên theo thứ tự đường chéo zigzag, cách nhau bởi một dấu cách.

Subtasks

• Subtask 1 (30% số điểm): ~1 ≤ n, m ≤ 50~
• Subtask 2 (70% số điểm): ~1 ≤ n, m ≤ 1000~

Sample Test

Input:

3 3
1 2 3
4 5 6
7 8 9

Output:

1 2 4 7 5 3 6 8 9

Input:

2 4
1 2 3 4
5 6 7 8

Output:

1 2 5 6 3 4 7 8

Cho ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~. Bạn hãy đếm số phần tử lẻ nằm trong mảng.

Input

• Dòng đầu chứa số nguyên dương ~N~ (~N \leq 10^6~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~ (~a_i \leq 10^9~).

Output

• In ra số lượng phần tử lẻ có trong mảng.

Sample Test

Input

3
1 2 3

Output

2

Cho hai số nguyên dương ~a~ và ~b~. Tính tổng tất cả các số nguyên dương ~x~ thỏa mãn:

• ~x~ là ước của a
• ~3x~ là ước của b

Input

• Gồm ~2~ số nguyên dương ~a~ và ~b~ ~(1 \le a,b \le 10^{12})~.

Output

• In ra tổng tất cả các số nguyên dương ~x~ thỏa mãn điều kiện trên. Dữ liệu đảm bảo kết quả không quá ~10^{18}~. Nếu không có giá trị ~x~ thỏa mãn thì kết quả được xem là ~0~.

Subtask

• Có ~80\%~ số test ứng với ~0 < a,b \le 10^6~.
• Có ~20\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

4 18

Sample Output 1

3

Sample Input 2

1 2

Sample Output 2

0

Một công ty cần mua ~N~ lít sữa. Có ~M~ người nông dân cung cấp sữa, người nông dân thứ ~i~ có ~A_i~ lít sữa và bán với giá ~P_i~ cho mỗi lít.

Công ty có thể mua sữa từ nhiều người nông dân khác nhau. Hãy tính số tiền ít nhất mà công ty cần bỏ ra để mua đủ ~N~ lít sữa. Dữ liệu đảm bảo tổng lượng sữa của tất cả nông dân luôn lớn hơn hoặc bằng ~N~.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~.
  ~(0 ≤ N ≤ 10^9,\ 1 ≤ M ≤ 10^6)~
• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~P_i~ và ~A_i~ ~(0 ≤ P_i ≤ 10^9,\ 1 ≤ A_i ≤ 10^9)~, lần lượt là giá 1 lít sữa và lượng sữa mà người nông dân thứ ~i~ có.

Output

• In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất để mua đủ ~N~ lít sữa.

Sample Test

Input:

100 5
5 20
9 40
3 10
8 20
6 30

Output:

650

Input:

10 3
3 5
2 8
4 10

Output:

22

Scoring

• Subtask 1 (40% số điểm): ~N ≤ 10^6,\ A_i ≤ 10^6~
• Subtask 2 (60% số điểm): Không có ràng buộc gì thêm.

Cho ba số nguyên dương ~a,l,r~ (~1 \leq a \leq 10^{10}~, ~1 \leq l \leq r \leq 10^{10}~).

Yêu cầu: Tìm max ~a~ ~mod~ ~i~ với ~l \leq i \leq r~.

Input

• Dòng đầu tiên chứa số nguyên ~T~ ~(1 \leq T \leq 10)~ là số bộ test.
• ~T~ dòng tiếp theo mỗi dòng gồm ba số nguyên dương ~a,l,r~.

Output

• In ra ~T~ kết quả thỏa mãn yêu cầu bài toán.

Sample Input 1

1
15 4 10

Sample Output 1

7

Sample Input 2

2
21 11 89
5 5 5

Sample Output 2

21
0

Scoring

• Subtask ~1 \ (30\%)~: ~1\le a,l,r \le 10^5~.
• Subtask ~2 \ (70\%)~: ~1\le a,l,r \le 10^{10}~.

Phát minh mới nhất của của Nitori là một chiếc máy bay ném bom điều khiển từ xa. Ba nàng tiên ánh sáng đã đặt một chiếc cho kế hoạch khủng bố đền Hakurei.

Dĩ nhiên để máy bay có thể hoạt động thì cần có pin. Mỗi cục pin có 3 thông tin: ~e_i, w_i, c_i~ lần lượt và mức năng lượng, khối lượng và giá thành. Thời gian bay của máy bay được xác định bằng công thức: ~E\over{W}~ trong đó ~E~ là tổng mức năng lượng và ~W~ là tổng khối lượng của tất cả pin và khối lượng của máy bay.

Để đảm bảo kế hoạch thành công, máy bay cần hoạt động lâu nhất có thể. Ba nàng tiên có ngân sách ~b~ và khối lượng của máy bay là ~w~, hãy giúp họ chọn pin sao cho thời gian bay là lâu nhất!

Input:

• Dòng đầu chứa số ~n,b,w (1≤n×b≤10^5,1≤w≤1000)~.
• ~n~ dòng tiếp theo mỗi dòng chứa ba số ~e_i,w_i,c_i (0≤e_i,w_i≤1000,0≤c_i≤b)~ là mức năng lượng, khối lượng và giá thành của cục pin thứ ~i~.

Output:

• In ra tổng thời gian bay của máy bay, sai số không quá ~10^{-3}~.

Sample Test:

Input:

10 1000 20
40 40 40
1 1 1
70 30 60
100 20 700
80 50 200
30 1 200
100 100 1
20 1 500
30 20 100
70 50 100

Output:

3.1707

Giới hạn

• 25% số điểm ~n≤20~.
• 25% số điểm ~w_i=0~.
• 25% số điểm ~c_1=c_2=...=c_n~.
• 25% số điểm không có ràng buộc gì thêm.

Đằng sau một lập trình viên thành công là một cô bạn gái... không tồn tại 🗿

Nhân dịp sinh nhật, Tèo được thưởng một chiếc điện thoại Nakio. Một ngày nọ, mải chụp ảnh up story, cậu vô tình làm rơi chiếc điện thoại của mình làm cho bàn phím của nó hoạt động một cách rất ảo diệu. Khi nhấn vào một phím, chiếc điện thoại lại hiện ra các ký tự của phím khác. May mắn thay là không có hai phím nào hoạt động giống nhau nên Tèo vẫn có thể viết được tất cả các chữ cái. Sau một hồi tìm hiểu, cậu ấy đã tìm được cách hoạt động của các phím.

Đây là cách thức hoạt động của bàn phím điện thoại khi nó vẫn chưa bị hỏng. Bàn phím hoạt động gần tương tự với bộ gõ T9 trên những chiếc điện thoại cục gạch quen thuộc của nhiều thế hệ. Muốn gõ được chữ a, ta cần nhấn phím 2 một lần; muốn gõ được chữ b, ta cần nhấn phím 2 hai lần. Nếu muốn viết hai chữ cái nằm trên cùng một phím thì sau khi gõ chữ cái đầu tiên, ta cần nhấn phím # một lần rồi sau đó gõ chữ cái tiếp theo. Ví dụ, muốn viết xâu abc, ta cần nhấn theo thứ tự 2#22#222. Phím 0 hoạt động như dấu cách, 1 và * không hoạt động.

Tèo vừa chia tay với người yêu nên cậu ấy muốn up story suy suy thất tình lên mạng xã hội F bằng chiếc điện thoại của mình. Hãy chỉ ra thứ tự các phím cần nhấn để viết được dòng caption đó.

Input

• Dòng đầu tiên chứa ~9~ số nguyên phân biệt từ ~1~ đến ~9~ có ý nghĩa: Số thứ ~1~ là cách hoạt động của phím 1, số thứ ~2~ là cách hoạt động của phím 2, ..., số thứ ~9~ là cách hoạt động của phím 9 (nghĩa là nếu số thứ ~2~ là 3 thì lúc này phím 2 sẽ hoạt động như phím 3).
• Dòng thứ hai là một xâu gồm các chữ cái tiếng Anh viết thường (có thể có dấu cách) có độ dài không quá ~100~ là nội dung của story mà Tèo muốn up lên trang F. Dữ liệu đảm bảo sau ký tự cuối cùng của caption không có dấu cách.

Output

Một xâu mô phỏng thứ tự các phím cần nhấn để viết được dòng caption của Tèo.

Scoring

• Subtask 1 [50%]: Bàn phím của Tèo không bị hỏng. Nói cách khác, ở dòng đầu tiên, số thứ ~i~ có giá trị là ~i~ ~(1\le i\le 9)~.
• Subtask 2 [50%]: Không có ràng buộc gì thêm.

Ví dụ

Input

1 2 3 4 5 6 7 8 9
den do roi kia minh dung lai em nhe

Output

3#3366036660777666444055444206444664403886640555244403360664433

Input

4 6 2 5 1 7 9 3 8
nhin sang trai vi em khong phai cua anh

Output

2211#111220666632210966631110999111088204411222#221061131110333993032211