Để tham gia câu lạc bộ Origami của trường, Huy phải:

"Viết chương trình kiểm tra xem 3 số nguyên dương nhập vào có thể là 3 cạnh của một tam giác KHÔNG cân hay không."

Vì laptop của Huy đã bị hỏng, bạn hãy giúp Huy giải bài tập trên. Biết rằng tam giác đều là tam giác cân.

Input

• Một dòng duy nhất gồm 3 số nguyên dương \(a,b,c \left(a,b,c\leq 10^{18}\right)\)

Các số trên một dòng của input file được ghi cách nhau bởi dấu cách

Output

• Ghi ra "YES" nếu 3 số nguyên dương là 3 cạnh của của một tam giác KHÔNG cân, ngược lại in ra "NO"

Example

3 4 5 

YES

Đan định nghĩa một bảng số kích thước \(3 \times 3\) được gọi là bảng đẹp nếu tổng mỗi hàng, tổng mỗi cột đều bằng nhau và bảng có ít nhất hai phần tử có giá trị khác nhau.

Yêu cầu: Cho một bảng số kích thước \(3 \times 3\), hãy kiểm tra xem bảng số có phải là bảng đẹp hay không?

Input

• Gồm ba dòng, mỗi dòng gồm ba số nguyên có giá trị tuyệt đối không vượt quá \(10^{9}\).

Output

• In một dòng chứa xâu YES hoặc NO tương ứng cho câu trả là là bảng đẹp hoặc không phải là bảng đẹp.

Example

1 2 3
2 3 1
3 1 2

YES

1 1 1
1 1 1
1 1 1

NO

Hãy viết chương trình thực hiện nhiệm vụ sau:

Nhập vào từ bàn phím một xâu kí tự \(S\), hãy in ra số kí tự chỉ xuất hiện đúng 1 lần trong xâu \(S\).

Input

• Dòng đầu tiên và duy nhất chứa 1 xâu \(S\) (chỉ chứa các kí tự trong tập \(\{a,b,\dots z\}\), không chứa dấu cách) \((|S| \leq 255)\).

Output

• In ra số kí tự chỉ xuất hiện đúng 1 lần trong xâu \(S\).

Example

abbacdmedc 

2

Trong không khí rộn ràng của ngày Nhà giáo Việt Nam 20/11, Đức, một học sinh đam mê toán học, quyết định tổ chức một buổi thi đố thú vị cho các bạn trong lớp để tri ân thầy cô giáo. Cậu muốn thử thách các bạn với một bài toán liên quan đến các con số để thể hiện sự khéo léo và thông minh mà thầy cô đã dạy.
Đức đưa ra câu đố như sau:

• Cho hai số nguyên dương \(a\) và \(b\); hãy đếm số lượng các số có đúng ba ước trong đoạn từ \(a\) đến \(b\).

Input

• Một dòng duy nhất chứa hai số nguyên \(a\) và \(b\) \((1 \leq a < b \leq 10^9)\).

Output

• In ra một số nguyên duy nhất là số lượng các số có ba ước trong đoạn từ \(a\) đến \(b\).

Example

1 16

2

Vào dịp Giáng sinh, Santa Claus muốn tặng những món quà tri thức cho trẻ em trên khắp thế giới. Ông đã chuẩn bị \(n\) quyển sách giá lần lượt là \(a_1, a_2, ... , a_n (1 \leq a_i \leq 1.000.000)\) (đồng) và \(m\) quyển vở có giá là \(b_1, b_2, ... , b_m (1 \leq b_i \leq 1.000.000)\) (đồng). Để phù hợp với ngân sách mà mình đang có thì mỗi gói quà ông sẽ gói gồm 1 quyển sách và 1 quyển vở sao cho tổng giá trị của chúng không lớn hơn \(k\).
Yêu cầu: Cho biết \(k\), tính xem có thể gói được nhiều nhất bao nhiêu gói quà.

Input

• Dòng đầu tiên ghi ba số nguyên dương \(n\), \(m\) và \(k\) \(( 1 \leq n, m \leq 200.000 ; 1 \leq k \leq 200.000)\)
• Dòng thứ hai ghi \(n\) số nguyên dương \(a_1, a_2,..., a_n (1 \leq a_i \leq 10^6)\).
• Dòng cuối cùng ghi \(m\) số nguyên dương \(b_1, b_2,..., b_m (1 \leq b_i \leq 10^6)\).

Output

• In ra một số nguyên duy nhất là số gói kẹo nhiều nhất có thể gói được.

Example

5 5 10
4 7 3 2 6
1 8 9 3 1

4

Giới hạn

• Có \(50\)% số test ứng với \(n \leq 2000\);
• Có \(50\)% số test còn lại không có giới hạn gì thêm.

Cho một xâu \(s\) độ dài \(n\). Các ký tự từ trái sang phải được đánh số từ \(1\) tới \(n\).

Với mỗi \(i\) từ \(1\) tới \(n\), ta thực hiện thao tác sau: Đẩy các ký tự trong tiền tố độ dài \(i\) của \(s\) sang phải \(1\) đơn vị theo vòng tròn.

Điều đó có nghĩa là từ xâu \(s_1 s_2 s_3 \dots s_i\) sẽ biến thành \(s_2 s_3 s_4 \dots s_i s_1\)

Hãy cho biết kết quả của xâu \(s\) sau \(n\) thao tác.

Input

• Gồm 1 dòng duy nhất chứa xâu \(s\).

Output

• Gồm 1 dòng duy nhất chứa xâu kết quả.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 300\)
• Subtask \(2\) (\(28\%\) số điểm): \(n \le 3000\)
• Subtask \(3\) (\(52\%\) số điểm): \(n \le 300000\)

Example

dxmhloventha

vhednltmhoax

Lại là thực hiện truy vấn!

Lần này, bạn được cho một mảng \(a\) có \(n\) phần tử. Ban đầu, tất cả các phần tử trong mảng \(a\) có giá trị bằng \(0\). Bạn phải thực hiện \(Q\) truy vấn, mỗi truy vấn thuộc một trong hai dạng:

• 1 l r x: Tăng toàn bộ các phần tử trong mảng \(a\) từ vị trí \(l\) đến vị trí \(r\) một giá trị bằng \(x\).
• 2 l r x: Giảm toàn bộ các phần tử trong mảng \(a\) từ vị trí \(l\) đến vị trí \(r\) một giá trị bằng \(x\).

Yêu cầu: In ra dãy \(a\) sau \(Q\) truy vấn?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,Q\) (\(n,Q \le 10^5\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một truy vấn mô tả như trên (\(1 \le l \le r \le n, 1 \le x \le 10^3\)).

Output

• Một dòng chứa \(n\) số nguyên là dãy \(a\) sau truy vấn. Lưu ý nếu có tồn tại các số \(0\) đằng sau cũng cần in đủ.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n,Q \le 100\).
• Subtask \(2\) (\(70\%\) số điểm): không có ràng buộc gì thêm.

Example

5 3
1 1 2 1
1 2 3 1
2 4 5 1

1 2 1 -1 -1

Bạn được cho một dãy số \(a\) gồm \(n\) số nguyên. Nhiệm vụ của bạn là tìm số cặp số \((i,j) \ 1 \leq i \leq j \leq n\) sao cho \(a_i + a_{i+1} + ... + a_j = 0\)

Input

• Dòng đầu tiên chứa số nguyên dương \(n \ (1 \leq n \leq 10^5)\) - là số phần tử của mảng.
• Dòng thứ hai chứa \(n\) số nguyên, số thứ \(i\) là \(a_i\) \(( \mid a_i\mid \leq 10^9)\)

Output

• Số lượng cặp số \((i,j)\) thõa mãn điều kiện trên

Example

4
-3 3 -4 4

3

Cho một dãy \(a\) gồm \(n\) phần tử nguyên không âm.

Hãy đếm số đoạn con liên tiếp \([l,r]\) của dãy \(a\) sao cho tổng của đoạn con đó bằng độ dài của đoạn, hay \(a_l + a_{l+1} + ... + a_r = r - l + 1\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\).
• Dòng thứ hai gồm \(n\) số nguyên không âm miêu tả dãy \(a\).

Output

• In ra số đoạn con thỏa mãn.

Điều kiện

• \(1 \le n \le 2*10^5\).
• \(0 \le a \le 9\).

Subtask

• \(50\%\) số điểm: \(n \le 1000\).
• \(50\%\) số điểm: \(n \le 2*10^5\).

Example

3
1 2 0 

3

5
1 1 0 1 1 

6

Cho \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) rải đều trên một đường tròn theo chiều kim đồng hồ. Hãy tìm cung tròn có độ dài nhỏ nhất mà tổng các số trên cung tròn lớn hơn hoặc bằng \(S\). In ra số lượng số trên cung tròn đó. Nếu không có cung tròn nào thỏa mãn thì in ra \(-1\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, S \ (S \leq 10^{18})\).

• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)\)

Output

• In ra độ dài cung tròn tìm được

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 100\)
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 2000\)
• Subtask \(3\) (\(40\%\) số điểm): \(n \leq 200000\)

Example

5 7
3 1 1 1 4 

2

5 6
1 1 1 1 4

3

7 80
70 11 32 43 43 11 54

2