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.

Cho một kí tự ~c~. Liệu ~c~ có phải một chữ cái thuộc bảng chữ cái tiếng Anh hay không? Hãy kiểm tra xem!

Input

Gồm một ký tự ~c~ duy nhất.

Output

In ra YES nếu ~c~ thuộc bảng chữ cái tiếng Anh, ngược lại in ra NO.

Sample Test 1

Input:

a

Output:

YES

Sample Test 2

Input:

@

Output:

NO

Cho số nguyên dương ~n~. Hãy đưa ra số lượng chữ số của ~n~ và tổng các chữ số trong biểu diễn thập phân của ~n~.

Input

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

Output

Gồm hai dòng, dòng thứ nhất chứa số chữ số và dòng thứ hai chứa tổng chữ số của ~n~.

Sample Test

Input:

69

Output:

2
15

Hai xâu được gọi là anagram của nhau nếu xâu này là một hoán vị của xâu kia.

Cho hai xâu ký tự ~X~ và ~Y~, hãy cho biết 2 xâu có phải là anagram của nhau hay không.

Input

Gồm hai dòng, mỗi dòng chứa một xâu có độ dài không quá ~10^5~ kí tự.

Output

In ra YES nếu hai xâu là anagram của nhau, ngược lại in ra NO.

Sample Test 1

Input:

dear
read

Output:

YES

Sample Test 2

Input:

dead
dae

Output:

NO

Cho một dãy ~A~ gồm ~n~ số nguyên ~a_{1}, a_{2}, a_{3}, ..., a_{n}~. Hãy tìm đoạn con đan dấu dài nhất của dãy ~A~.

Note:

• Một đoạn con đan dấu của dãy ~A~ là một đoạn liên tiếp ~a_{l}, a_{l + 1}, a_{l + 2}, ..., a_{r}~ ~(l \leq r)~ sao cho ~\forall i: l \leq i < r~, ~a_{i}~ khác dấu ~a_{i + 1}~.
• Số ~0~ không khác dấu với các số khác.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \leq n \leq 10^5~).
• Dòng tiếp theo chứa ~n~ số nguyên ~a_{1}, a_{2}, a_{3}, ..., a_{n}~ (~|a_{i}| \leq 10^5~).

Output

• Dòng thứ nhất in ra độ dài đoạn con đan dấu dài nhất của dãy ~A~.
• Dòng tiếp theo in ra các số trong đoạn con đan dấu dài nhất, mỗi số cách nhau một khoảng trắng. Nếu có nhiều đoạn thoả mãn hãy in ra đoạn xuất hiện đầu tiên trong dãy.

Sample Test 1

Input:

5
-3 6 -2 9 5

Output:

4
-3 6 -2 9

Sample Test 2

Input:

6
1 -3 6 2 -9 5

Output:

3
1 -3 6

Note: Có hai đoạn đan dấu là ~[1, -3, 6]~ và ~[2, -9, 5]~, ta chỉ lấy đoạn xuất hiện đầu tiên.

Stop learning useless algorithms, go and solve some problems, learn how to use binary search 😈 - Um_nik

~x~ và ~y~ là hai số nguyên thoả mãn ~|x+y|=2023~.

Cho trước số nguyên ~x~. Hãy tìm ~y~ để ~x-y~ đạt giá trị nhỏ nhất.

Dữ liệu

Nhập vào số nguyên ~x~ ~(|x| \le 10^9)~.

Kết quả

In ra giá trị nhỏ nhất của ~x-y~.

Ví dụ

Input

1

Output

-2021

There are 10 types of people in this world: Those who understand binary and those who don't 😈

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

Hãy tính tổng của chữ số đầu tiên và chữ số cuối cùng của ~N~.

Dữ liệu

Nhập vào số nguyên dương ~N~ ~(N \le 10^9)~.

Kết quả

In ra một số nguyên là đáp án của bài toán trên.

Ví dụ

Input

29042024

Output

6

Ràng buộc

• Subtask ~1~ ~(60\%)~: ~N \le 100~.
• Subtask ~2~ ~(40\%)~: Không có ràng buộc gì thêm.

There are two ways to write error-free programs; only the third one works 😈

Cho một số nguyên ~N~ ~(0 \le N \le 10^{18})~ Đếm xem có bao nhiêu bộ hai số nguyên dương chẵn ~a, b~ sao cho ~a * a * b * b = N~.

Lưu ý: ~a~ và ~b~ có vài trò khác nhau. Ví dụ: cặp ~(6, 4)~ và ~(4, 6)~ được tính là hai cặp khác nhau.

Input:

• Dòng đầu tiên gồm số nguyên ~N~.

Output:

• In ra một số nguyên là số lượng cặp ~a~ và ~b~ thỏa mãn đề bài .

Scoring:

• Subtask ~1~ ~(40\%)~: ~N \le 10^6~;
• Subtask ~2~ ~(40\%)~: ~N \le 10^{12}~;
• Subtask ~3~ ~(20\%)~: ~N \le 10^{18}~.

Sample Input

16

Sample Output

1

Cho hai số nguyên dương ~x, \; k~.

Tìm số nguyên dương ~y~ bé nhất sao cho ~x \times y~ chia hết cho ~k~.

Input:

• Gồm một dòng duy nhất ghi ~2~ số nguyên ~x, \; k~.

Output:

• Gồm một số nguyên dương là kết quả của bài toán.

Scoring:

• Subtask ~1~ ~(50\%)~: ~ x, \; y \leq 10^6~.
• Subtask ~2~ ~(50\%)~: ~ x, \; y \leq 10^{18}~.

Sample Input 1

5 2

Sample Output 1

2

It's not a bug, it's a feature 😈

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

Hãy đếm số cặp số ~(x, y)~ nguyên dương thoả mãn:

• ~1\le x, y \le N~.
• ~x+y~ là số nguyên tố.

Dữ liệu

Nhập vào số nguyên dương ~N~ ~(1\le N \le 10^6)~.

Kết quả

In ra số cặp ~(x, y)~ thoả mãn

Ví dụ

Input

3

Output

5

Giải thích

Các cặp số ~(x, y)~ thoả mãn: ~(1, 1), (1, 2), (2, 1), (2, 3), (3, 2)~.

Ràng buộc

• Subtask ~1 \ (60\%)~: ~N \le 100~.
• Subtask ~2 \ (40\%)~: Không có ràng buộc gì thêm.

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

Cho dãy số ~A~ gồm ~N~ phần tử nguyên dương và một số nguyên dương ~K~. Tìm hai dãy con liên tiếp của dãy ~A~, mỗi dãy gồm đúng ~K~ phần tử (hai dãy không giao nhau), sao cho chênh lệch tổng các phần tử của hai dãy là lớn nhất.

Input:

• Dòng đầu tiên gồm hai số nguyên dương ~N, K~ ~(2 \le N \le 10^6, 1 \le K \le N / 2)~;
• Dòng thứ hai gồm ~N~ số nguyên dương có giá trị không quá ~10^9~ mô tả dãy số ~A~.

Output:

• In ra một số nguyên dương là giá trị chênh lệch lớn nhất tìm được.

Scoring:

• Subtask ~1~ ~(60\%)~: ~ N \le 100~;
• Subtask ~2~ ~(20\%)~: ~ N \le 10^3 ~;
• Subtask ~3~ ~(20\%)~: Không có giới hạn gì thêm.

Sample Input 1

5 2
1 3 2 1 8

Sample Output 1

5

Cho dãy số nguyên dương ~A~ có ~N~ phần tử và một số nguyên không âm ~K~ cho trước. Một dãy số chẵn lẻ đẹp của dãy ~A~ là dãy con liên tiếp thoả mãn:

• Có ít nhất một số chẵn và ít nhất một số lẻ trong dãy con;
• Gọi ~x~ là tổng các số chẵn, ~y~ là tổng các số lẻ trong dãy con thì ~0 \le x - y \le K~ Đếm số lượng các dãy số chẵn lẻ đẹp của dãy ~A~.

Input:

• Dòng đầu tiên gồm hai số nguyên dương ~N, K~;
• Dòng thứ hai gồm ~N~ số nguyên dương có giá trị không quá ~10^9~ mô tả dãy số ~A~.

Output:

• In ra một số nguyên dương là kết quả của bài toán.

Scoring:

• Subtask ~1~ ~(40\%)~: ~ N \le 200; K \le 10^6 ~;
• Subtask ~2~ ~(30\%)~: ~ N \le 2000; K \le 10^6 ~;
• Subtask ~3~ ~(20\%)~: ~ N \le 2*10^5; K = 0 ~;
• Subtask ~4~ ~(10\%)~: ~ N \le 2*10^5; K \le 100 ~;

Sample Input 1

5 5
1 3 2 9 10

Sample Output 1

3

Sample Input 2

3 1
1 3 1

Sample Output 2

0