Contest #03/2022

Bạn X thiết kế ra một máy đánh số thứ tự có ba chữ số, nên được giao nhiệm vụ đánh mã số lên các thiết bị của công ty. Chiếc máy đánh số từ \(001, 002, 003, \dots, 997, 998, 999\) rồi sau đó quay lại \(001, 002, 003, \dots\).

Hãy cho biết, thiết bị thứ \(n\) có mã số là bao nhiêu?

Input

• Một số \(n\) duy nhất (\(n \le 10^9\)).

Output

• In ra một số duy nhất là mã số của thiết bị thứ \(n\).

Example

275

275

1000

001

2275

277

Scoring

• \(60\%\) số test có \(n \le 10^5\).
• \(40\%\) số test còn lại có \(n \le 10^9\).

Cho một mảng \(A\) có \(n\) phần tử. Hãy tìm chênh lệch nhỏ nhất giữa hai phần tử bất kỳ của \(A\).

Input

• Dòng đầu tiên chứa một số \(n\) \((n \le 10^5)\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa một số \(A_i\) \((A_i \le 10^9)\).

Output

• In ra kết quả là chênh lệch nhỏ nhất giữa hai phần tử bất kỳ của \(A\).

Example

5
2 
4 
1 
8 
2

0

5
20 
9 
2 
5 
13

3

Scoring

• 60% số test có \(n \le 10^3\).
• 40% còn lại có \(n \le 10^5\).

Ta định nghĩa một phép nhân giữa một chuỗi \(a\) và một số nguyên dương \(x\): \(a.x\) là một chuỗi được hình thành bằng cách sao chép \(x\) lần chuỗi \(a\).

Ví dụ: abc\(.2\) = abcabc, a\(.5\) = aaaaa.

Một chuỗi \(a\) được gọi là chia hết cho chuỗi \(b\) nếu tồn tại một số nguyên \(x\) sao cho \(b.x\) = \(a\).

Ví dụ abababab chia hết cho chuỗi ab, nhưng không chia hết cho ababab hoặc a.

\(LCM\) của hai chuỗi \(s\) và \(t\) là chuỗi ngắn nhất khác rỗng sao cho chuỗi \(s\) và chuỗi \(t\) chia hết cho chuỗi đó.

Bạn được cho hai chuỗi \(s\) và \(t\). Hãy tìm \(LCM(s, t)\).

Input

• Dòng đầu tiên gồm một số nguyên \(q\) (\(1\leq q \leq 2000\)) là số lượng test case.
• Mỗi test case gồm hai dòng, chứa hai chuỗi \(s\) và \(t\) (\(1 \leq |s|, |t| \leq 20\)). Mỗi kí tự trong chuỗi là một trong hai kí tự a hoặc b.

Output

• Với mỗi test case, in ra bội chung nhỏ nhất \(LCM(s, t)\) nếu tồn tại, ngược lại in ra -1.

Example

3
baba
ba
aa
aaa
aba
ab

baba
aaaaaa
-1

Phi hành đoàn trên con tàu vũ trụ Chết chóc phải hoàn thành các nhiệm vụ để vận hành và duy trì con tàu. Vì trong số họ có các imposter đang chực chờ cơ hội để tiêu diệt họ, một số người đã đi thành cặp để bảo vệ lẫn nhau. Tuy nhiên không phải cặp nào cũng đủ sức mạnh để chống trả lại bọn imposter gian ác. Tất cả các phi hành đoàn sẽ mang 1 con số báo danh trong đoạn từ \(L\) đến \(R\) và imposter nhận ra rằng, một cặp đôi \(a\) và \(b\) là bất khả chiến bại nếu như tổng số ước của \(a\) không bao gồm \(a\) bằng \(b\) và ngược lại tổng số ước của \(b\) không bao gồm \(b\) bằng \(a\). Là 1 imposter, bạn hãy lập trình để xác định những cặp bất khả chiến bại này để loại trừ ra nhằm tiêu diệt những nhóm yếu ớt hơn.

Yêu cầu: Cho 2 số nguyên dương \(L\) và \(R\) (\(L < R\)). Hãy đếm số lượng cặp \((a, b)\) mà \(L \le (a, b) \le R\) và đó là cặp đôi bất khả chiến bại, cặp \((a, b)\) và \((b, a)\) được tính là 1.

Input

• Gồm 1 dòng duy nhất 2 số nguyên dương \(L, R\) (\(L \le R \le 10^6\)).

Output

• Số lượng cặp bất khả chiến bại.

Example

219 285

1

Bằng cách xếp những khối lập phương lại với nhau, ta có thể tạo nên những kim tự tháp cho riêng mình.

Vậy cần bao nhiêu khối lập phương để tạo nên một tháp lá bài có độ cao \(n\).

Input

• Dòng đầu, chứa số nguyên dương \(T\) (\(T \le 10^6\)) - số lượng câu hỏi.
• \(T\) dòng sau, mỗi dòng chứa một số nguyên dương \(n\) (\(n \le 10^9\)).

Output

• Gồm \(T\) dòng, mỗi dòng chứa số lượng khối lập phương tối thiểu để tạo một tháp có chiều cao \(n\) tương ứng (lấy số dư khi chia cho \(10^9 + 7\)).

Example

3
1
2
3

1
10
35