Bài tập

Nhập vào 4 số nguyên a, b, c, d. Nếu a và b là giá trị lớn nhất trong các số, thì in ra a + b. Ngược lại nếu c và d là giá trị lớn nhất trong các số, thì in ra c + d. Ngược lại in ra a + b + c + d.

Example

6 14 5 13

38

10 5 8 4

27

8 8 8 2

16

1 12 2 13

28

Viết chương trình nhập vào hai dãy số nguyên dương \(a\) và \(b\). Dãy \(a\) có \(N\) phần tử, dãy \(b\) có \(M\) phần tử. Đếm số lượng giá trị trong đoạn \([1, 1000]\), xuất hiện ở cả hai dãy \(a\) và \(b\).

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(M\) - số lượng phần tử dãy \(a\) và dãy \(b\). \((1 \leq N, M \leq 1000)\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(a_1, a_2, ..., a_N\) - giá trị các phần tử của dãy \(a\) \((1 \leq a_i \leq 1000)\).
• Dòng thứ ba gồm \(M\) số nguyên dương \(b_1, b_2, ..., b_M\) - giá trị các phần tử của dãy \(b\) \((1 \leq b_i \leq 1000)\).

Output

Một dòng duy nhất là số lượng giá trị nằm trong đoạn \([1, 1000]\) xuất hiện ở cả hai dãy \(a\) và \(b\).

Example

5 6
2 2 3 3 4
2 3 4 6 8 2

3

Mật mã để mở kho báu được giấu trong một xâu kí tự.
Xâu kí tự này gồm \(4\) loại kí tự là a, b, c, d và kí tự 0.

Đặc biệt, xâu kí tự này có thể nối hai đầu lại với nhau để tạo thành một vòng tròn.
Ngoài ra, ta có thể thay mỗi kí tự 0 bằng một kí tự bất kì trong các kí tự từ a đến d.

Mật mã của xâu được định nghĩa là độ dài lớn nhất của một xâu con liên tiếp chỉ chứa đúng một loại kí tự.

Yêu cầu:
Hãy xác định mật mã lớn nhất có thể đạt được sau khi thay thế các kí tự 0 một cách hợp lí.

\InputFile

Gồm một dòng duy nhất chứa xâu \(S\) gồm các kí tự a, b, c, d và 0.
Độ dài của xâu không vượt quá \(10^5\).

\OutputFile

In ra một số nguyên dương duy nhất --- giá trị mật mã của xâu.

\Scoring

• Có \(50\%\) số test ứng với độ dài xâu \(\le\) 1000.

Example

0ddc0ba

3

0dc0b

3

Cho dãy số nguyên dương \(A\) gồm \(n\) phần tử.
Hãy đếm số lượng dãy con (không nhất thiết liên tiếp) có trung bình cộng bằng đúng \(k\).

Input

Vào từ file văn bản DAYCON.INP:

• Dòng 1: số bộ test \(T \le 10\).

• Mỗi test gồm:

• Một dòng: \(n, k\) (\(1 \le n, k \le 200\)).

• Một dòng: \(a_1, a_2, \dots, a_n\) với \(1 \le a_i \le 200\).

Output

Ghi ra file văn bản DAYCON.OUT:

Với mỗi test, in ra một dòng --- số lượng dãy con có trung bình bằng \(k\), modulo \(10^9 + 7\).

Example

3
4 6
5 7 6 7
5 100
4 2 5 10 5
6 100
77 97 114 105 115 97

5
0
1

Scoring

• Subtask 1 (20%): \(n \le 16\), \(k, a_i \le 50\).
• Subtask 2 (40%): \(n \le 30\), \(k, a_i \le 50\).
• Subtask 3 (40%): Không có ràng buộc thêm.