Cho một xâu \(S\) chỉ chứa chữ cái in thường và chữ cái in hoa. Một xâu được gọi là xâu đẹp nếu tất cả vị trí kí tự lẻ \((1,3,5,7,...)\) đều là chữ cái thường và tất cả vị trí kí tự chẵn \((2,4,6,8,...)\) đều là chữ cái in hoa.

Biết rằng \(S_i\) là vị trí kí tự thứ \(i\) và xâu có vị trí bắt đầu từ \(1\).

Yêu cầu: Cho một xâu \(S\), bạn hãy xác định xem \(S\) có phải là xâu đẹp không.

Input

• Chứa một xâu \(S\) duy nhất (độ dài của xâu \(S\) không quá \(1000\)).

Output

• In ra Yes nếu \(S\) là xâu đẹp, in ra No nếu \(S\) không phải xâu đẹp.

Example

dEcOdEkHoNg

Yes

DECOKHOKHONG

No

Cho một dãy số gồm \(n\) số nguyên dương \(a_1,a_2,...,a_n\).

Yêu Cầu: Bạn hãy đếm cặp \((i,j)\) thỏa mãn tất cả các điều kiện sau:

• \(1 \le i < j \le n\).
• \(min(a_i,a_j) = i\).
• \(max(a_i,a_j) = j\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \le n \le 5 \times 10^5)\).
• Dòng tiếp theo chứa dãy số nguyên dương \(a_1,a_2,...,a_n\) \((1 \le a_i \le n)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(1 \le n \le 5000\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
1 3 2 4

2

Cho \(q\) truy vấn, mỗi truy vấn gồm \(3\) số nguyên dương \(a, l, r\) , yêu cầu tính số lượng số \(x\) sao cho:

• \(l \le x \le r\)
• \(x\) or \(a = x\)

Bạn có thể tham khảo phép or tại đây

Input

• Dòng đầu tiên là số \(q\) \((1 \le q \le 10^5)\).
• \(q\) dòng tiếp theo, mỗi dòng là \(3\) số \(a, l, r\) \((1 \le a, l, r \le 10^9)\).

Output

• Gồm \(q\) dòng, mỗi dòng là đáp án cho \(1\) truy vấn.

Scoring

Subtask \(1\) (\(20\%\) số điểm): Có \(1 \le q \le 2000\), \(1 \le a, l, r \le 2000\).
Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm

Example

1
1 2 5

2

Bạn có một dãy số gồm \(n\) số nguyên dương \(a_1,a_2,a_3,\ldots,a_n\) và số nguyên dương \(k\).

Bạn sẽ làm thao tác này tối đa \(k\) lần:

• Chọn \(i \ \in [1;n]\) và cộng \(1\) vào \(a_i\). \(( * )\)

Bạn cần làm theo thao tác \(( * )\) sao cho \(gcd(a_1,a_2,\ldots,a_n)\) đạt giá trị lớn nhất có thể. Lưu ý rằng bạn có thể làm thao tác đó ít hơn hoặc bằng \(k\) lần (bạn có thể không cần làm theo và tính luôn).

Biết rằng \(gcd(a,b)\) là ước chung lớn nhất của \(a\) và \(b\).

Yêu Cầu: Bạn hãy lập chương trình giải quyết bài toán trên.

Input

• Dòng đầu tiên chứa số nguyên dương \(n,k\) \((2\ \le n\ \le3\times{10}^5, 1\ \le k\ \le\ {10}^{18})\).
• Dòng còn lại chứa \(n\) số nguyên dương \(a_1,a_2,\ldots,a_n\) \((1\ \le a_i\ \le\ 3\times{10}^5)\), mỗi số cách nhau một khoảng trắng

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Có \(2 \le n \le 5\) và \(1 \le k \le 2 \times n\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 6
3 4 9

5

3 4
30 10 20

10