Bài tập

Cho dãy \(A\) gồm \(N\) số nguyên dương \(a_{1}, a_{2}, … ,a_{N}\) và một số nguyên dương \(K\) . Một đoạn con của \(A\) là một dãy liên tục các phần tử của \(A\). Một đoạn con của \(A\) được gọi là hài hòa nếu trung bình cộng của các phần tử trong đoạn con đó đúng bằng \(K\).

Yêu cầu: Hãy tìm đoạn con hài hòa dài nhất bằng cách chỉ ra độ dài và chỉ số phần tử đầu tiên của đoạn con đó. Nếu tồn tại nhiều đoạn con như vậy thì đưa ra đoạn con có chỉ số của phần tử đầu tiên nhỏ nhất. Nếu không tồn tại đoạn con nào thỏa mãn thì ghi ra số \(0\).

Input

Đọc từ tệp văn bản BAI4.INP có cấu trúc:

--- Dòng đầu tiên ghi hai số nguyên dương \(N\) và \(K\) \((1 ≤ N ≤ 10^5), 1 ≤ K ≤ 10^9)\);

--- Dòng thứ hai chứa \(N\) số nguyên \(a_{1}, a_{2}, … ,a_{N}\) \((1 ≤ a_{i} ≤ 10^9, i = 1, 2, … , N)\);

--- Các số cách nhau một dấu cách.

Output

Ghi ra tệp văn bản BAI4.OUT hai số nguyên dương là độ dài và chỉ số phần tử đầu tiên của đoạn con tìm được, các số ghi trên một dòng và cách nhau một dấu cách hoặc ghi ra số \(0\) nếu không tồn tại đoạn con nào thỏa mãn điều kiện của bài toán.

Example

5 3
1 2 3 4 6

3 2

4 3
1 2 5 6

0

Scoring

--- Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(N ≤ 100\).

--- Có \(60\%\) số test tương ứng với \(60\%\) số điểm có \(N ≤ 5000\).

--- \(10\%\) còn lại không có ràng buộc gì thêm.

--- Thời gian thực hiện mỗi test không quá một giây.

Hãy tìm tất cả các số nguyên tố trong đoạn [\(A;B\)]

Input

• Gồm 2 số nguyên \(A;\ B\) cách nhau bởi 1 dấu cách (\(1\leq A\leq B\leq 10^7\))

Output

• Ghi ra tất cả các số nguyên tố trong khoảng [\(A;B\)]. Mỗi số trên 1 dòng.

Example

1 10

2
3
5
7

Cho tập hợp \(S\) gồm \(n\) xâu kí tự: \(S_1, S_2, \dots, S_n\). Kí tự trong các xâu này có thể là a hoặc b.

Một xâu \(A\) được gọi là xâu hoán vị của xâu \(B\), nếu ta có thể tạo ra được xâu \(A\) bằng cách sắp xếp lại các kí tự của xâu \(B\). Hãy tạo tập hợp \(S'\) theo nguyên tắc sau: với mỗi xâu \(S_i\) \((1 \le i \le n)\), ta thêm tất cả các xâu hoán vị của \(S_i\) vào \(S'\). Nói cách khác, \(S'\) là tập hợp các xâu hoán vị của \(n\) xâu thuộc \(S\).

Ta tiến hành dựng cây trie của tập xâu \(S'\) vừa tạo. Hãy cho biết cây trie này có bao nhiêu nút.

Nhắc lại về Trie

**Trie** là một cấu trúc dữ liệu dạng cây dùng để lưu trữ một danh sách các xâu với bộ kí tự hữu hạn, cho phép việc lưu trữ các xâu hiệu quả có tiền tố giống nhau.

Cây trie được dựng theo nguyên tắc: mỗi nút liên kết với một xâu ký tự sao cho các xâu ký tự của tất cả các nút con của một nút đều có chung một tiền tố, chính là xâu ký tự của nút đó. Nút gốc tương ứng với xâu ký tự rỗng.

Ví dụ, với các xâu `aba`, `abb`, `acb`, ta dựng được một cây trie gồm $7$ nút như sau:

\begincenter

\endcenter

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 20)\) là số lượng xâu trong tập \(S\).

• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(S_i\) \((1 \le |S_i| \le 10^5)\), các kí tự của xâu chỉ có thể là a hoặc b.

Output

• In ra một số nguyên duy nhất là phần dư của đáp án bài toán khi chia cho \(10^9+7\).

Example

1
abaa

14

2
abb
aaa

11

4
aa
ab
bb
aba

10

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(|S_i| \leq 20\).

• Subtask \(2\) (\(20\%\) số điểm): \(n = 1, |S_i| \leq 10^3\).

• Subtask \(3\) (\(15\%\) số điểm): \(n = 2, |S_i| \leq 10^3\).

• Subtask \(4\) (\(10\%\) số điểm): \(|S_i| \leq 10^3\).

• Subtask \(5\) (\(15\%\) số điểm): \(n = 1\).

• Subtask \(6\) (\(10\%\) số điểm): \(n = 2\).

• Subtask \(7\) (\(10\%\) số điểm): Không có ràng buộc gì thêm.

Cho một cái cây có \(n\) nút và ta định nghĩa \(1\) là nút gốc của cây.

Bây giờ ta có \(q\) truy vấn, mỗi truy vấn có dạng: \(l_{i}\) \(r_{i}\) (\(1 \leq l_{i} \leq r_{i} \leq n\)).

Yêu cầu: Ứng với mỗi truy vấn, ta in ra LCA của tất cả các nút từ nút \(l_{i}\) đến nút \(r_{i}\)

Input

• Dòng thứ nhất chứa số n (\(2 \leq n \leq 300000\)) - Thể hiện số nút của cây

• \(n−1\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(x,y\) - Thể hiện cạnh nối giữa hai đỉnh \(x\) và \(y\)

• Dòng tiếp theo, chứa số \(q\) (\(1 \leq q \leq 300000\)) - Thể hiện số lượng truy vấn

• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_{i}\), \(r_{i}\) (\(1 \leq l_{i} \leq r_{i}\leq n\))

Output

• Ứng với mỗi truy vấn, in ra đáp án cần tìm.

Example

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

4
1

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(2 \leq n,q \leq 20\).

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