Cho một số tự nhiên ~n~. Tính tổng ~1 + 2 + 3 + ... + n~.

Input

Gồm một số ~n~ duy nhất. (~n \leq 3 \times 10^5~)

Output

In ra tổng cần tìm.

Sample Test

Input:

5

Output:

15

Cho một số tự nhiên ~N~. Hãy in ra cụm từ tdz ~N~ lần, các cụm cách nhau bởi một dấu cách.

Input

Một số tự nhiên ~N~ duy nhất. (~N \leq 10^5~)

Output

Một dòng gồm toàn cụm tdz theo yêu cầu đề bài.

Sample Test

Input:

3

Output:

tdz tdz tdz

Dino chọn tất cả các số tự nhiên từ ~a~ đến ~b~. Daisy chọn tất cả các số tự nhiên từ ~c~ đến ~d~. Hỏi hai bạn có chọn số nào giống nhau không?

Input

Gồm bốn dòng, mỗi dòng chứa lần lượt các số nguyên ~a~, ~b~, ~c~, ~d~. (~0 \leq a \leq b \leq 1000~, ~0 \leq c \leq d \leq 1000~)

Output

In ra YES nếu hai bạn chọn có số chung, ngược lại in ra NO.

Sample Test 1

Input:

5 
10 
15 
20

Output:

NO

Note:

• Dino chọn các số từ ~5~ đến ~10~: ~5, 6, 7, 8, 9, 10~
• Daisy chọn các số từ ~15~ đến ~20~: ~15, 16, 17, 18, 19, 20~
• Do các số hai bạn chọn không giống nhau nên kết quả là NO.

Sample Test 2

Input:

1 
4
2
6

Output:

YES

Note:

• Dino chọn các số từ ~1~ đến ~4~: ~1, 2, 3, 4~
• Daisy chọn các số từ ~2~ đến ~6~: ~2, 3, 4, 5, 6~
• Do các số hai bạn cùng chọn số ~2, 3, 4~ nên kết quả là YES.

Quá chán với việc xây dựng trang web lập trình, TDZ quyết định xây dựng một nhà mạng HNOJ mới để giúp coder dễ dàng trò chuyện, chia sẻ kinh nghiệm và chia sẻ code. Tuy nhiên, để duy trì nhà mạng HNOJ hoạt động thì cần phải có kinh phí, và TDZ quyết định sẽ bắt người dùng trả tiền để sử dụng dịch vụ.

Cụ thể, nhà mạng HNOJ quy định một tin nhắn cơ sở gồm 30 kí tự (sang kí tự thứ 31 sẽ tính đến tin nhắn thứ hai). Giá cước của mỗi tin nhắn cơ sở là 3 doge coin vì hiện tại lạm phát đang tăng cao.

Bây giờ, với mỗi một tin nhắn, bạn hãy tính thử xem bạn cần trả bao nhiêu doge coin cho nhà mạng HNOJ nhé.

Input

Gồm một xâu ~S~ khác rỗng có độ dài không quá 1000 ký tự thuộc bảng mã ASCII.

Output

In ra số doge coin cần trả dể gửi một tin nhắn ~S~ đó.

Sample Test 1

Input:

Hello, World!

Output:

3

Sample Test 2

Input:

Never gonna give you up. Never gonna let you down. Never gonna run around and desert you...

Output:

12

Để tiếp tục nâng cao trải nghiệm cho người dùng, nhà mạng HNOJ tiếp tục xây dựng dịch vụ kiểm tra số dư tài khoản chỉ với một nút gửi. Bạn vừa gửi yêu cầu kiểm tra tài khoản và nhận được thông báo, hãy tính số tin nhắn bạn còn có thể gửi được với số dư hiện tại, với chi phí cho mỗi tin nhắn cơ sở vẫn giữ là ~3~ dogecoin.

Input

Gồm một xâu có dạng:

So du tai khoan: x dogecoin

Với x là số dư hiện tại của người dùng (~x~ nguyên dương, ~|x| \leq 3000~).

Output

In ra số lượng tin nhắn cơ sở bạn có thể gửi được với số dư x.

Sample Test

Input:

So du tai khoan: 200 dogecoin

Output:

66

Cho một số nguyên dương ~n~. Hãy liệt kê tất cả số nguyên tố nhỏ hơn hoặc bằng ~n~.

Input

Gồm một số nguyên dương ~n~ duy nhất (~2 \leq n \leq 10^5~).

Output

In ra tất cả các số nguyên tố không vượt quá ~n~ theo thứ tự tăng dần trên cùng một dòng.

Sample Test

Input:

14

Output:

2 3 5 7 11 13

Cho hai xâu ~S~ và ~T~, hãy kiểm tra xem ~T~ có phải là một xâu con liên tiếp của ~S~ hay không.

Input

Gồm hai dòng, dòng thứ nhất chứa xâu ~S~ và dòng thứ hai chứa xâu ~T~. Độ dài các xâu không vượt quá 100 ký tự.

Output

In ra YES nếu ~T~ là xâu con liên tiếp của ~S~, ngược lại in ra NO.

Sample Test

Input:

abba
ab

Output:

YES

TDZ đang học về ước chung lớn nhất (~UCLN~). Nhưng khi nghe đến thứ gọi là "ước nguyên tố" thì TDZ đang rất mơ hồ vì cậu không nắm vững kiến thức về số nguyên tố. Vì vậy, TDZ nhờ bạn giải giúp bài tập này để thông não ra một tí:

Cho ~n~ số nguyên dương, hãy:

• Đếm số lượng số nguyên tố trong ~n~ số này.
• Tìm ~UCLN~ của ~n~ số này.

Input

• Dòng thứ nhất gồm một số nguyên dương ~n~ (~n \leq 10^5~).
• Dòng thứ hai gồm ~n~ số nguyên dương có giá trị không vượt quá ~10^5~.

Output

• Dòng thứ nhất in ra số lượng số nguyên tố trong ~n~ số.
• Dòng thứ hai in ra ~UCLN~ của ~n~ số.

Subtasks

• Subtask ~1~ (~50\%~): Tất cả các số trong input nhỏ hơn ~10^3~.
• Subtask ~2~ (~50\%~): Không thay đổi.

Sample Test 1

Input:

5
3 6 2 9 5

Output:

3 
1

Note:

• Có ~3~ số nguyên tố là ~3, 2, 5~.
• ~UCLN(3, 6, 2, 9, 5) = 1~

Sample Test 2

Input:

4
4 8 10 6

Output:

0
2

Cho số nguyên dương ~N~.

Yêu cầu: Tính giá trị của:

Input

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

Output

In ra kết quả cần tìm. Kết quả được coi là đúng nếu sai số không vượt quá ~10^{-18}~.

Sample Test

Input

5

Output

0.833333333333333333

Giải thích

~S = \dfrac{1}{1 \times 2} + \dfrac{1}{2 \times 3} + \dfrac{1}{3 \times 4} + \dfrac{1}{4 \times 5} + \dfrac{1}{5 \times 6} = \dfrac{5}{6} = 0.8(3)~.

Cho ~n~ số nguyên dương. Hãy đưa ra ước chung lớn nhất của ~n~ số đó.

Input

• Dòng thứ nhất chứa số nguyên dương ~n~ (~n \leq 1000~).
• Dòng thứ hai chứa ~n~ số nguyên dương không vượt quá ~10^6~.

Output

In ra ước chung lớn nhất của ~n~ số.

Sample Test 1

Input:

4
2 4 6 8

Output:

2

Sample Test 2

Input:

4
1 2 4 5

Output:

1

Một cặp số sinh đôi là hai số nguyên tố có khoảng cách là 2 đơn vị. Cho một số nguyên dương ~n~, hãy đưa ra số lượng các cặp số sinh đôi khác nhau mà các số đều không vượt quá ~n~.

Hai cặp số sinh đôi được gọi là khác nhau nếu chúng không phải hoán vị của nhau, hay nói cách khác tồn tại ít nhất một số chỉ thuộc một cặp duy nhất. Ví dụ:

• ~(3, 5)~, ~(5, 7)~ là hai cặp số sinh đôi khác nhau.
• ~(3, 5)~, ~(5, 3)~ không là hai cặp số sinh đôi khác nhau.

Input

Gồm một số nguyên dương ~n~ duy nhất (~n \leq 1000~).

Output

In ra số lượng các cặp số sinh đôi theo yêu cầu đề bài.

Sample Test

Input:

7

Output:

2

Note:

• Hai cặp số thoả mãn là ~(3, 5)~ và ~(5, 7)~.

Cho một số nguyên dương chẵn ~n~. Hãy liệt kê tất cả các cách phân tích ~n~ thành tổng của hai số ~a~ và ~b~ sao cho: ~ \begin{cases} a \leq b\\ a, b \text{ nguyên tố} \\ a + b = n \end{cases} ~

Input

Gồm một số nguyên dương chẵn ~n~ duy nhất (~n \leq 1000~).

Output

• Dòng thứ nhất chứa số ~k~ - số lượng cách phân tích khác nhau.
• ~k~ dòng tiếp theo, mỗi dòng chứa hai số ~a~ và ~b~ thoả mãn yêu cầu đề bài. Các cặp số ~(a, b)~ có thể được in theo thứ tự bất kì.

Sample Test 1

Input:

10

Output:

2
3 7
5 5

Sample Test 2

Input:

18

Output:

2
7 11
5 13

Hãy viết chương trình nhập một xâu và viết xâu đó theo chiều dọc.

Input

Gồm một xâu S duy nhất. Độ dài xâu S không vượt quá ~1000~ và xâu S không bao gồm dấu cách.

Output

In ra các ký tự của xâu S lần lượt trên các dòng khác nhau.

Sample Input

Input:

Hello

Output:

H
e
l
l
o

Cho một xâu ~S~, hãy đếm số lần xuất hiện của các chữ số ~0~, ~1~, ~2~,..., ~9~ trong xâu ~S~.

Input

Gồm một xâu ~S~ duy nhất chứa các ký tự là chữ cái và chữ số, độ dài không quá ~100~ ký tự.

Output

Gồm 10 dòng, dòng thứ ~i~ in ra số lượng chữ số (~i - 1~) xuất hiện trong dãy ~S~.

Sample Test

Input:

a1bc321

Output:

0
2
1
1
0
0
0
0
0
0

Cho một xâu kí tự ~S~. Hãy liệt kê tất cả các từ trong xâu ~S~ trên các dòng khác nhau (Mỗi từ là một dãy kí tự khác kí tự trắng liên tiếp nhau).

Input

Gồm một xâu kí tự ~S~ duy nhất có độ dài không vượt quá ~1000~ ký tự.

Output

• Dòng đầu tiên in ra số ~k~ - số lượng từ trong xâu ~S~.
• ~k~ dòng tiếp theo, mỗi dòng lần lượt in ra các từ trong xâu ~S~ theo thứ tự xuất hiện của chúng.

Sample Test

Input:

abc cba ddd

Output:

3
abc
cba
ddd

Một đoạn văn bản hoàn chỉnh là đoạn văn bản không có kí tự trắng (dấu cách) dư thừa:

• Không có dấu cách ở đầu đoạn.
• Giữa các từ chỉ tồn tại một kí tự trắng.

Cho một dãy các ký tự ~S~, hãy đưa ra dãy ~S~ sau khi được sửa thành đoạn văn bản hoàn chỉnh.

Input

Gồm một dãy ~S~ chỉ chứa các kí tự trắng hoặc các chữ cái Tiếng Anh (~|S| \leq 1000~).

Output

In ra ~S~ là đoạn văn bản hoàn chỉnh.

Sample Test

Input:

   Ha Noi    Online      Judge

Output:

Ha Noi Online Judge

Tên tệp của một file Python bắt buộc gồm hai phần, ngăn cách bởi một dấu chấm .:

• Phần tên: Là một xâu không rỗng, gồm các kí tự từ a đến z, A đến Z, 0 đến 9, dấu gạch dưới (_) hoặc dấu gạch ngang (-).
• Phần mở rộng: Là xâu py, không phân biệt chữ hoa chữ thường.

Ví dụ:

• Tên file Python hợp lệ: a.py, Hello-world.py, tXz_69420.Py.
• Tên file Python không hợp lệ: among us.py (chứa dấu cách), 6/9/2022.py (chứa dấu /), pa064.cpp (sai phần mở rộng).

Bạn được cho một xâu, hãy kiểm tra xem xâu đó liệu có thể là tên hợp lệ cho một file Python không nhé.

Input

Gồm một xâu S khác rỗng có độ dài không quá 100 ký tự thuộc bảng mã ACSII.

Output

In ra YES nếu S là tên file Python hợp lệ, ngược lại in ra NO.

Sample Test 1:

Input:

helloWorld.py

Output:

YES

Sample Test 2:

Input:

pythonIntro.docx

Output:

NO

Sample Test 3:

Input:

test_ko_sai_nhe_hehe.py

Output:

YES

Dữ liệu đảm bảo để bài luôn có kết quả!

Xét hai số nguyên dương ~u, v~, ta gọi thao tác ghép hai số ~u, v~ là thao tác viết số ~v~ sau số ~u~.

Ví dụ: Với ~u = 123, v = 456~, sau khi ta ghép hai số ~u, v~ với nhau, ta được số ~123456~.

Cho ~n~ số nguyên dương ~a_1, a_2, ..., a_n~.

Hãy cho biết: Có bao nhiêu cặp chỉ số ~(i, j) \ (1 \le i \lt j \le n)~ sao cho khi ta thực hiện thao tác ghép hai số ~a_i, a_j~, ta được một số mới chia hết cho ~3~?

Input

• Dòng đầu tiên chứa số nguyên dương ~n \ (n \ge 2);~
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n.~

Output

In ra kết quả là số cặp chỉ số ~(i, j)~ thoả mãn đề bài.

Scoring

• Subtask 1 [20%]: ~n \le 1000; \ a_i \le 10^9;~
• Subtask 2 [40%]: ~n \le 10^5; \ a_i \le 10^{18};~
• Subtask 3 [40%]: ~n \le 10^5; \ a_i \le 10^{100}.~

Examples

Input

7
123 4 5 7 10 3 2

Output

7

Giải thích: Các cặp chỉ số thoả mãn yêu cầu đề bài là: ~(1, 6), (2, 3), (2, 7), (3, 4), (3, 5), (4, 7), (5, 7).~

Cho dãy số nguyên ~a = (a_1, a_2, ..., a_n)~ bạn được thay số ~0~ trong ~a~ bởi một số nguyên bất kỳ khác sau đó chọn ra trong dãy ~a~ một số nhiều nhất các số (không cần đúng thứ tự) sao cho các số đã chọn tạo thành một dãy số nguyên liên tiếp.

Yêu cầu: Tìm cách có được dãy số nguyên liên tiếp dài nhất theo cách trên.

Ví dụ với ~a = (1, 0 ,3 ,8 ,5 ,9 ,0)~, ta có thể thay hai số ~0~ lần lượt bởi ~6~ và ~7~, khi đó có thể chọn trong ~a~ ra các số ~(5, 6, 7, 8, 9)~ để được dãy số nguyên liên tiếp dài nhất.

INPUT

Dòng 1 chứa số nguyên dương ~n \le 10^6~

Dòng 2 chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ cách nhau bởi dấu cách (giá trị ~i~: ~|a_i| \le 10^6~)

OUTPUT

Số nguyên duy nhất là độ dài dãy số nguyên liên tiếp thu được theo phương án của bạn.

SAMPLE INPUT

7
1 0 3 8 5 9 0

SAMPLE OUTPUT

5

Trong lớp học toán ngày hôm nay của Cirno, cô ra một bài toán cho các học sinh của mình:

Cho một số nguyên dương, hãy đếm số cách xóa bỏ một chữ số (số còn lại có thể có số 0 ở đầu) để số còn lại chia hết cho 3, nhưng không chia hết cho 9 (vì cô không thích số 9).

Input:

• Một số nguyên dương ~n \le 10^{100000}~.

Output

• Số cách xóa thỏa mãn.

Sample Test

Input:

396

Output:

2

Giới hạn

• 60% số điểm: ~n \le 10^{1000}~
• 40% số điểm: Không có giới hạn gì thêm.

Cho mảng ~A~ có ~n~ phần tử nguyên dương, hãy chọn một tập con có ít nhất ba phần tử (không cần liên tiếp) của ~n~ phần tử sao cho tổng ba số bất kỳ trong tập con đã chọn không lớn hơn tổng các số còn lại trong mảng ~A~ và số lượng phần tử của tập con là lớn nhất.

INPUT

Dòng đầu tiên ghi số ~n~ (~4 \le n \le 10^4~)

Dòng tiếp theo ghi ~n~ số nguyên dương ~A_1, A_2, ..., A_n~ (~A_i \le 10^2~)

OUTPUT

Dòng duy nhất ghi số lượng phần tử được chọn

Nếu không thể chọn được tập con thoả mãn thì in ra ~0~

SAMPLE INPUT

8
6 9 4 3 7 2 5 1

SAMPLE OUTPUT

7

Giải thích: Các phần tử được chọn là ~6, 4, 3, 7, 2, 5, 1~

Cho một dãy số nguyên dương ~a~, đếm số lượng dãy con liên tiếp có tổng chia hết cho ~d~

Hai dãy con được gọi là khác nhau nếu ít nhất một trong hai điểm đầu hoặc điểm cuối hay dãy con đó trong dãy gốc là khác nhau.

Ví dụ:

• Với ~d = 4~, dãy (~2, 1, 2, 1, 4, 1~) có ~4~ dãy con thoả mãn là (~1, 2, 1~), (~1, 2, 1, 4~), (~4~), (~2, 1, 4, 1~)

• Với ~d = 2~, dãy (1, 1, 1, 1) có ~4~ dãy con thoả mãn

INPUT

Dòng đầu tiên là số ~t~ - số lượng test (~t \le 100~)

~t~ nhóm dòng tiếp theo, mỗi nhóm dòng tương ứng với một yêu cầu:

• Dòng đầu là hai số nguyên dương ~d~ và ~n~ (~d \le 10^6~, ~n \le 5 * 10^4~)

• Dòng thứ hai chứa ~n~ số nguyên dương biểu diễn dãy số

OUTPUT

~t~ dòng là kết quả của các test theo thứ tự

SAMPLE INPUT

1
2 4
1 1 1 1

SAMPLE OUTPUT

4

Giải thích: Các cặp (~i, j~) sau thoả mãn: (~1, 2~), (~2, 3~), (~3, 4~), (~1, 4~)

debugging /diːˈbʌɡɪŋ/ (v.): Being the detective in a crime movie where you are also the murderer.

MrTee đang có một dãy gồm ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ và cũng có một chiếc máy quét mới mua (ở Ý, rất đắt). Khi đặt chiếc máy quét vào vị trí thứ ~i~, chiếc máy sẽ hiện số lượng các số mà bằng với ~a_i~ trong dãy mà có khoảng cách tới ~i~ không quá ~K~, kể cả chính nó. Vì quá mệt mỏi vì học sinh quá báo trong kì thi vừa rồi, MrTee đã nhờ bạn giúp MrTee thử chiếc máy này xem ở mỗi vị trí ~i~ từ ~1~ đến ~N~, chiếc máy sẽ trả về giá trị bao nhiêu.

Nói cách khác, cho một dãy ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~, với mỗi ~i~, bạn cần tìm số lượng số ~j~ thỏa mãn ~a_i = a_j~ và ~|i - j| \le K~ ~(1 \le i, j \le N)~.

Liệu bạn có phải pro player hay cũng báo thầy như học sinh của MrTee?

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N, K~ ~(K \le N)~.
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^5)~.

Output

• Gồm một dòng gồm ~N~ số nguyên, số thứ ~i~ là đáp án nếu ta đặt máy quét vào vị trí thứ ~i~.

Scoring

• Subtask 1 ~(60 \%)~: ~K \le N \le 2000~.
• Subtask 2 ~(40 \%)~: ~K \le N \le 10^5~.

Sample Input

6 2
1 1 2 2 2 1

Sample Output

2 2 3 3 3 1

Trên trục số ~Ox~, cho ~𝑁~ đoạn thẳng, mỗi đoạn thẳng được xác định bởi hai điểm đầu và cuối là hai số nguyên. Một điểm ~𝑀~ được gọi là nằm trong đoạn thẳng ~𝐴𝐵~ nếu ~𝐴 ≤ 𝑀 ≤ 𝐵~.

Yêu cầu: Đếm xem có bao nhiêu điểm có toạ độ nguyên nằm trong đúng ~𝐾~ đoạn thẳng.

Dữ liệu nhập vào từ file văn bản DC.INP:

• Dòng đầu tiên gồm hai số nguyên ~𝑁~ và ~𝐾~ ~(1 ≤ 𝐾 ≤ 𝑁 ≤ 10^5);~
• ~𝑁~ dòng sau, mỗi dòng gồm hai số nguyên ~𝑎, 𝑏~ mô tả hai điểm đầu và cuối của đoạn thẳng ~(1 ≤ 𝑎 ≤ 𝑏 ≤ 10^{18})~.

Kết quả ghi ra file văn bản DC.OUT:

Một số nguyên duy nhất là số lượng điểm có toạ độ nguyên nằm trong đúng ~𝐾~ đoạn thẳng.

Ràng buộc

• Có ~50\%~ số test ứng với ~50\%~ số điểm của bài thoả mãn: ~𝑎, 𝑏 ≤ 10^3;~
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thoả mãn: ~𝐾 = 𝑁;~
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

3 2
1 5
2 8
3 7

Output

3

Giải thích: Toạ độ của ~3~ điểm nằm trong đúng ~2~ đoạn thẳng là: ~2, 6, 7~.

• Điểm có toạ độ ~2~ nằm trong ~2~ đoạn thẳng: đầu tiên và thứ hai.
• Điểm có toạ độ ~6, 7~ nằm trong ~2~ đoạn thẳng: thứ hai và thứ ba.

Input

3 1
1 5
2 8
3 7

Output

2   

Giải thích: Toạ độ của ~2~ điểm nằm trong đúng ~1~ đoạn thẳng là: ~1, 8~.

• Điểm có toạ độ ~1~ chỉ nằm trong đoạn thẳng đầu tiên.
• Điểm có toạ độ ~8~ chỉ nằm trong đoạn thẳng thứ ba.

Input

3 3
1 5
2 8
3 7

Output

3

Giải thích: Toạ độ của ~3~ điểm nằm trong cả ~3~ đoạn thẳng là: ~3,4,5~.

Cho hai đường thẳng ~d_1: y = y_1~ và ~d_2: y = y_2~. Cho ~n~ điểm phân biệt trên đường thẳng ~d_1~ (có hoành độ ~x_{11}~, ~x_{12}~, ..., ~x_{1n}~) và ~m~ điểm phân biệt trên đường thẳng ~d_2~ (có hoành độ ~x_{21}~, ~x_{22}~, ..., ~x_{2m}~). Hãy tìm khoảng cách Manhattan nhỏ nhất giữa hai điểm ~(A, B)~ với ~A \in d_1~ và ~B \in d_2~ và đếm số cặp điểm ~(A, B)~ phân biệt có khoảng cách Manhattan nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~, ~m~ (~n, m \le 10^6~)
• Dòng thứ hai chứa hai số nguyên ~y_1~, ~y_2~ (~-10^9 < y_1, y_2 < 10^9~)
• Dòng thứ ba chứa ~n~ số nguyên phân biệt ~x_{11}~, ~x_{12}~, ..., ~x_{1n}~ (~-10^9 < x_{1i} < 10^9~)
• Dòng thứ tư chứa ~m~ số nguyên phân biệt ~x_{21}~, ~x_{22}~, ..., ~x_{2m}~ (~-10^9 < x_{2i} < 10^9~)

Output

• Một dòng duy nhất gồm hai số nguyên: khoảng cách Manhattan ngắn nhất và số cặp có khoảng cách như vậy.

Sample Test

Input

3 4
1 -2
3 0 6
5 -2 4 2

Output

4 3

Giải thích

Có ~3~ cặp điểm ~(A, T)~, ~(A, Z)~, ~(C, X)~

Công ty đồ chơi của hoangduong nhập khẩu ~n~ con búp bê kachusa. Các con búp bê được đánh số từ ~1~ tới ~n~ trong đó con búp bê thứ ~i~ là một hộp rỗng có kích thước là một số nguyên ~a_i~. Người ta có thể lồng con búp bê thứ ~i~ vào trong con búp bê thứ ~j~ nếu con búp bê thứ ~j~ đang rỗng và ~a_i + k \le a_j~, với ~k~ là một số nguyên dương cho trước. Bằng cách lồng các con búp bê vào nhau theo cách như vậy, công ty của hoangduong chỉ cần tìm chỗ đặt những con búp bê ngoài cùng (những con búp bê không nằm trong bất kỳ con búp bê nào khác) vào kho.

Yêu cầu: Hãy giúp hoangduong lồng các con búp bê vào nhau sao cho tổng kích thước các con búp bê ngoài cùng là nhỏ nhất.

INPUT

Dòng 1 chứa hai số nguyên dương ~n \le 10^5~; ~k \le 10^9~ cách nhau một khoảng trắng.

Dòng 2 chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^9~), mỗi số cách nhau một khoảng trắng.

OUTPUT

Là một số nguyên duy nhất là tổng kích thước các con búp bê ngoài cùng theo phương án tìm được.

SAMPLE INPUT

8 2
8 4 2 1 1 3 5 9

SAMPLE OUTPUT

18

Trong lúc buồn chán hoangduong đã tìm một xâu ~S~ có độ dài ~n~ kí tự là các chữ cái tiếng Anh in thường và đảo ngược một số xâu con liên tiếp của xâu ~S~. Hãy viết chương trình tìm xâu ~S~ sau khi hoangduong thực hiện lần lượt ~m~ lần đảo xâu như trên.

INPUT

• Dòng đầu tiên gồm một xâu ~S~ có độ dài ~n~ mà hoangduong tìm được bạn đầu (~1 \le n \le 200000~)
• Dòng thứ hai gồm một số nguyên ~m~ (~1 \le m \le 100000~) là số lẫn mà hoangduong đảo một xâu con liên tiếp của xâu ~S~
• Dòng thứ ba gồm ~m~ số tự nhiên ~a_i~ (~1 \le a_i \le n / 2~), mỗi số mô tả lần đảo một xâu con liên tiếp từ kí tự thứ ~a_i~ đến kí tự thứ ~n - a_i + 1~ của Na. Các kí tự trong ~S~ được đánh số từ ~1~ đến ~n~.

OUTPUT

Gồm một dòng duy nhất chứ một xâu là xâu ~S~ sau khi hoangduong đã thực hiện lần lượt ~m~ lần đảo

SAMPLE INPUT 1

kcchinbayble
4
2 2 2 2

SAMPLE OUTPUT 1

kcchinbayble

SAMPLE INPUT 2

haideu
1
1

SAMPLE OUTPUT 2

uediah

Đằ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

Cho một dãy gồm ~n~ số nguyên dương ~a_1, a_2, a_3, \ldots, a_n~ là hoán vị của các số nguyên từ ~1~ đến ~n~. Sử dụng các thao tác lần lượt đổi chỗ hai số ở vị trí ~i~ và ~j~ bất kỳ, hãy sắp xếp dãy ban đầu thành dãy tăng dần.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~n \leq 10^5~).
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, a_3, \ldots, a_n~ là hoán vị của các số nguyên từ ~1~ đến ~n~.

Output

• Dòng đầu tiên in ra số ~k~ (~0 \leq k \leq 2 \times 10^5~) - số lượng thao tác cần dùng.
• ~k~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~i~, ~j~ cách nhau một khoảng trắng (~1 \leq i, j \leq n~) thể hiện một thao tác đổi ~a_i~ và ~a_j~ cho nhau.

Có thể chứng minh được rằng luôn tồn tại cách sắp xếp thoả mãn không sử dụng quá ~2 \times 10^5~ thao tác.

Subtasks

• Subtask ~1~ (~10\%~): ~n = 3~.
• Subtask ~2~ (~20\%~): ~n \leq 100~.
• Subtask ~3~ (~30\%~): ~n \leq 10^4~.
• Subtask ~4~ (~40\%~): Không có ràng buộc gì thêm.

Sample Test

Input:

4
3 4 1 2

Output:

2
1 3
2 4

Một dãy số được gọi là ~''~đẹp~''~ nếu mỗi phần tử trong dãy đó đều có số lần xuất hiện không vượt quá ~2~. Ví dụ:

• ~[1, 5, 2, 4, 3], [6, 9, 9, 6], [100]~ là các dãy đẹp.
• ~[3, 3, 3, 4, 4], [7, 7, 8, 7]~ và ~[100, 100, 100]~ không phải là các dãy đẹp.

Cho dãy ~a~ có ~n~ phần tử, hãy đếm số cặp chỉ số ~(l, r)~ sao cho ~a_l, a_{l+1}, ..., a_r~ là dãy đẹp.

Input

• Dòng đầu tiên chứa số nguyên dương ~n;~
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n.~

Output

In ra kết quả là số cặp chỉ số ~(l, r)~ thoả mãn đề bài.

Scoring

• Subtask 1 [20%]: ~n \le 50; \ a_i \le 50;~
• Subtask 2 [15%]: ~n \le 500; \ a_i \le 500;~
• Subtask 3 [15%]: ~n \le 5000; \ a_i \le 5000;~
• Subtask 4 [50%]: ~n \le 5 \times 10^5; \ a_i \le 5 \times 10^5.~

Examples

Input

4
1 2 1 1

Output

9

Giải thích: Các cặp chỉ số ~(l, r)~ thoả mãn đề bài là: ~(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4).~

Input

6
4 5 4 5 4 5

Output

18