Trong chuỗi tín hiệu nhận được, hãy xác định xem từ khóa WINTER có xuất hiện theo đúng thứ tự hay không. Các chữ cái được phép nằm cách nhau; chúng không cần đứng liền kề.

Dữ liệu vào

Một dòng chứa chuỗi chữ in hoa Latin S (1 ≤ |S| ≤ 10^5).

Dữ liệu ra

In YES nếu WINTER là một dãy con của S; ngược lại, in NO.

Ví dụ

Input

WXXIYNTZEXR

Output

YES

Giới hạn

• 1 ≤ |S| ≤ 10^5
• S chỉ gồm các chữ cái A–Z.

Cho một mảng số nguyên và các truy vấn đoạn [L, R]. Với mỗi truy vấn, hãy tính phép XOR của các phần tử từ vị trí L đến R, kể cả hai đầu mút.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên N, Q.
• Dòng thứ hai chứa N số nguyên A_1, A_2, ..., A_N.
• Mỗi dòng trong Q dòng tiếp theo chứa hai số nguyên L, R.

Dữ liệu ra

Với mỗi truy vấn, in XOR của A_L, A_{L+1}, ..., A_R trên một dòng.

Giới hạn

• 1 ≤ N, Q ≤ 2·10^5.
• 0 ≤ A_i ≤ 10^9.
• 1 ≤ L ≤ R ≤ N.

Ví dụ

Input

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

Output

1
5
3
1

Cho một lưới gồm ~n~ hàng và ~m~ cột ô vuông đơn vị. Một hình chữ nhật là một khối ô liên tiếp theo hàng và cột, chứa ít nhất một ô.

Hãy đếm số cách chọn hai hình chữ nhật không có ô chung. Hai hình được phép chạm nhau ở biên, miễn là không dùng chung ô. Cặp hình chữ nhật (~A~, ~B~) và (~B~, ~A~) được tính là cùng một cách.

Cấu hình Input

• Một dòng chứa hai số nguyên ~n~ và ~m~ — lần lượt là số hàng và số cột của lưới.

Cấu hình Output

• In ra số cách chọn modulo ~10⁹ + 7~.

Giới hạn

• ~1 ≤ n, m ≤ 10⁷~.

Ví dụ

Input

1 3

Output

5

Giải thích: Trên lưới một hàng và ba cột, có 5 cặp hình chữ nhật rời nhau: ba cặp gồm hai ô đơn, ô thứ nhất cùng đoạn từ cột 2 đến 3, và đoạn từ cột 1 đến 2 cùng ô thứ ba.

Subtasks

Các test được chấm độc lập; không áp dụng chấm theo batch.

Khối Rubik 2×2×2 gồm sáu mặt, mỗi mặt có bốn ô. Sáu màu được ký hiệu bằng các chữ cái U, D, F, B, L, R, tương ứng với màu của các mặt.

Một thao tác là xoay một mặt 90° theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, khi nhìn trực tiếp vào mặt đó từ bên ngoài khối Rubik. Mỗi lần xoay 90° tính là một bước; do đó, xoay 180° tính là hai bước. Xoay toàn bộ khối Rubik không được tính là một thao tác.

Với trạng thái ban đầu được cho, hãy tìm số bước ít nhất để giải khối Rubik. Khối được xem là đã giải nếu bốn ô trên mỗi mặt cùng màu; hướng đặt của toàn bộ khối không ảnh hưởng đến kết quả.

Dữ liệu vào

Sáu dòng lần lượt mô tả các mặt U, D, F, B, L, R. Mỗi dòng gồm bốn ký tự, biểu diễn bốn ô trên mặt tương ứng theo thứ tự trong bảng dưới đây.

Các ký tự màu là U, D, F, B, L, R. Mỗi màu xuất hiện đúng bốn lần. Trạng thái được cho luôn hợp lệ và có thể nhận được bằng cách xoay một khối Rubik đã giải.

Dữ liệu ra

In một số nguyên — số bước ít nhất để giải khối Rubik.

Ví dụ

Input

UUUU
DDDD
RRFF
LLBB
FFLL
BBRR

Output

1

Giải thích: Ví dụ trên thu được khi xoay mặt U của khối đã giải 90° theo chiều kim đồng hồ, nên đáp án là 1.

Subtasks

Các test được chấm độc lập, mỗi test có trọng số bằng nhau; không áp dụng chấm theo batch.

Trong lễ hội mùa đông, có N điểm sáng nằm trên một trục thẳng. Tọa độ của chúng lần lượt là x_1, x_2, ..., x_N, với x_1 < x_2 < ... < x_N.

Ban tổ chức muốn chia các điểm sáng thành đúng K nhóm không rỗng. Mỗi nhóm gồm các điểm liên tiếp theo thứ tự tọa độ. Nếu một nhóm gồm các điểm từ l đến r, chi phí của nhóm là bình phương độ dài đoạn từ x_l đến x_r, tính cả hai đầu mút:

Chi phí = (x_r - x_l + 1)^2

Hãy tìm tổng chi phí nhỏ nhất có thể.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên N và K.
• Dòng thứ hai chứa N số nguyên x_1, x_2, ..., x_N theo thứ tự tăng dần.

Dữ liệu ra

In ra một số nguyên là tổng chi phí nhỏ nhất.

Giới hạn

• 1 <= K <= N <= 5000.
• 0 <= x_1 < x_2 < ... < x_N <= 10^6.

Ví dụ

Input

4 2
1 2 3 4

Output

8

Giải thích: Chia thành hai nhóm gồm các điểm [1, 2] và [3, 4]. Mỗi nhóm có độ dài 2, nên tổng chi phí là 2^2 + 2^2 = 8.

Phân nhóm điểm

Mỗi test được chấm độc lập; không áp dụng chấm theo batch.