Cho hai số nguyên dương \(n\) và \(k\). Hãy tìm số nguyên dương thứ \(k\) không chia hết cho \(n\).

Dữ liệu vào từ tệp văn bản BAI1.INP

• Dòng đầu tiên gồm số nguyên dương \(q\) (\(1 \le q \le 1000\)) - số truy vấn bạn cần trả lời.
• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(n\) và \(k\) (\(2 \le n \le 10^9, 1 \le k \le 10^9\)).

Kết quả ghi ra tệp văn bản BAI1.OUT

• Gồm \(q\) dòng, mỗi dòng là kết quả của truy vấn.

Scoring

Sample Input 1

6
3 7
4 12
2 1000000000
7 97
1000000000 1000000000
2 1 

Sample Output 1

10
15
1999999999
113
1000000001
1

Note

Ở truy vấn đầu tiên, các số không chia hết cho \(3\) là \(1, 2, 4, 5, 7, 8, 10, 11, 13, \ldots\) \(10\) là số nguyên dương thứ bảy không chia hết cho \(3\).

Cho xâu \(S\) gồm các chữ cái tiếng Anh in thường. Gọi \(f(S)\) là số lượng kí tự phân biệt của xâu \(S\). Ví dụ \(S =\) abccaaa, vậy \(f(S)=3\).

Với mỗi \(K\) có giá trị từ \(1\) đến \(f(S)\), hãy đếm số lượng xâu con \(X\) của \(S\) có \(f(X) = K\).

Dữ liệu vào:

Gồm một xâu \(S\) (có số lượng kí tự - kí hiệu là \(|S|\) không vượt quá \(10^6\)).

Kết quả ghi:

Gồm \(f(S)\) dòng, mỗi dòng là kết quả tương ứng khi \(K\) có giá trị từ \(1\) đến \(f(S)\).

Ví dụ

Input

abba

Output

5
5

Giải thích

Các xâu con có \(1\) kí tự phân biệt là (xâu được gạch chân): \(\underline{a} \textit{bba}, \textit{a}\underline{b}\textit{ba}, \textit{ab}\underline{b}\textit{a}, \textit{abb}\underline{a}, \textit{a}\underline{bb}\textit{a}\)

Các xâu con có \(2\) kí tự phân biệt là (xâu được gạch chân): \(\underline{ab}\textit{ba}, \underline{abb}\textit{a}, \underline{abba}, \textit{a}\underline{bba}, \textit{ab}\underline{ba}\)

Ràng buộc

• Có \(40\%\) số test ứng với \(40\%\) số điểm thoả mãn: \(|S|\le 10^2\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thoả mãn: \(|S|\le 2\times 10^3\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thoả mãn: \(|S|\le 10^5\);
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có ràng buộc gì thêm.

Một câu chuyện rất dài... thầy đã xoá đi...

\(n\) lon nước tăng lực của mrtee có độ phê lần lượt là \(a_1, a_2, \ldots, a_n\). Ban đầu, mrtee có sức hấp thụ dinh dưỡng là \(k\). Khi mrtee chuẩn bị uống một lon nước tăng lực, thầy sẽ phải vận nội công khiến cho \(k\) giảm đi \(1\) đơn vị. Và khi uống lon nước đó, mrtee sẽ được \(a_i \times k\) năng lượng. Mỗi lon chỉ được sử dụng tối đa \(1\) lần.

Giống như bao người khác, mrtee cũng có ngưỡng giới hạn cho sự tích trữ năng lượng của mình. Do đó, mrtee muốn đặt ra \(q\) câu hỏi. Trong mỗi câu hỏi, mrtee đưa ra một giá trị \(x\) và muốn bạn hãy tính xem mrtee có thể uống nhiều nhất bao nhiêu lon nước tăng lực sao cho tổng năng lượng thu được không vượt quá \(x\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, k\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\).
• Dòng thứ ba chứa số nguyên dương \(q\).
• \(q\) dòng cuối cùng, mỗi dòng chứa một số nguyên dương \(x\) đại diện cho một câu hỏi của mrtee.

Output

• Với mỗi câu hỏi, in ra một số nguyên không âm là kết quả của câu hỏi đó.

Điều kiện

• \(1 \le n \le k \le 10^5\).
• \(1 \le q, a_i \le 10^5\).
• \(1 \le x \le 10^{16}\).

Subtask

• \(25\%\) số điểm: \(n, q \le 10\).
• \(25\%\) số điểm: \(n, q \le 10^3\).
• \(25\%\) số điểm: Tất cả lon nước có độ phê bằng nhau.
• \(25\%\) số điểm: Không có ràng buộc gì thêm.

Ví dụ

Input:

3 5
3 2 4
4
1 13 17 100

Output:

0
1
2
3

Cho hai xâu \(a\) và \(b\), và một số phép biến đổi như sau lên xâu \(a\):

• Chèn: chèn thêm một phần tử vào xâu \(a\).
• Xóa: xóa đi một phần tử khỏi xâu \(a\).
• Thay thế: đổi giá trị của một phần tử bất kì tại xâu \(a\).

Hãy tìm cách thực hiện ít phép biến đổi nhất sao cho xâu \(a\) bằng xâu \(b\).

Input

• Gồm hai dòng là hai xâu \(a\) và \(b\).

Output

• In ra số phép biến đổi ít nhất để đưa xâu \(a\) bằng xâu \(b\).

Ví dụ

Input 1

cat
cut

Output 1

1

Input 2

sunday
saturday

Output 2

3

Cho một dãy số \(a_1, a_2, \ldots, a_n\) và số nguyên dương \(k\). Bạn hãy đếm số cách để chia dãy \(a\) thành một số dãy con liên tiếp thỏa mãn trong từng dãy con, các phần tử đôi một có giá trị bằng nhau. Ngoài ra, từng phần tử trong mảng \(a\) ban đầu phải nằm trong ít nhất một dãy con, đồng thời mỗi dãy con có độ dài không vượt quá \(k\).

Ví dụ, xét dãy \(a = [1, 1, 1, 1, 3, 2, 2, 4, 4, 4, 7]\) và \(k = 3\). Một vài cách chia thỏa mãn là:

• \([(1, 1), (1, 1), (3), (2, 2), (4, 4), (4), 7]\)
• \([(1), (1, 1, 1), (3), (2), (2), (4, 4, 4), 7]\).

Ví dụ cách chia không thỏa mãn:

• \([(1, 1, 1, 1), (3), (2, 2), (4, 4, 4), 7]\) (dãy con đầu tiên quá số lượng phần tử tối đa cho phép).
• \([(1, 1), (1, 1, 3), (2, 2, 2), (4, 4, 4), 7]\). (dãy con thứ hai các phần tử không bằng nhau).

Dữ liệu vào từ tệp văn bản BAI4.INP

• Dòng đầu tiên chứa số nguyên dương \(n\) là số phần tử của dãy \(a\) (\(1 \le n \le 2 \cdot 10^5\)).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)).
• Dòng cuối cùng chứa số nguyên dương \(k\) là số phần tử tối đa trong một nhóm \((1 \le k \le n)\).

Kết quả ghi ra tệp văn bản BAI4.OUT

• Một dòng duy nhất là kết quả bài toán. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho \(10^9 + 7\)

Scoring

Sample Input 1

4
3 1 1 1
2

Sample Ouput 1

3

Sample Input 2

11
1 1 1 1 3 2 2 4 4 4 7
3

Sample Output 2

56

Note

Ở test ví dụ đầu tiên, có \(3\) cách chia thỏa mãn là:

• \([(3), (1, 1), (1)]\).
• \([(3), (1), (1, 1)]\).
• \([(3), (1), (1), (1)]\).

Cho dãy số nguyên dương \(a[1], a[2], …, a[N]\). Xét cách chia dãy số \(a\) thành \(K\) nhóm sao cho mỗi nhóm chứa một đoạn liên tiếp các phần tử của \(a\). Gọi trọng số của một cách chia là tổng các phần tử lớn nhất của mỗi nhóm

Yêu cầu: Tìm cách chia dãy số \(a\) thành \(K\) nhóm sao cho trọng số của cách chia là nhỏ nhất

Dữ liệu

• Dòng 1: 2 số nguyên dương \(N\) và \(K\) (\(K \le N\))
• Dòng 2: Gồm \(N\) số nguyên dương \(a[1], a[2], …, a[N]\)

Kết quả:

• Ghi ra 1 số nguyên duy nhất là trọng số tìm được

Input 1

    5 1
    1 2 3 4 5   

Output 1

    5

Input 2

    5 2
    1 2 3 4 5   

Output 2

```
6

Giới hạn:

• 14% số điểm: \(1\le N\le100, K\le min(N, 5)\)
• 18% số điểm: \(1\le N\le20\)
• 21% số điểm: \(1\le N\le100\)
• 47% số điểm: \(1\le N\le100000, K\le min(N, 100).\)

Sủi là người có máu M nên layout 40% là chưa đủ khổ. Sủi làm một chiếc bàn phím mới có dạng \(m\) chữ cái đầu của bảng chữ cái tiếng Anh nằm cạnh nhau. Cậu cần đánh một đoạn văn bản \(s\) có độ dài \(n\) chỉ gồm các chữ cái trong bàn phím. Sủi sẽ gõ từng chữ lần lượt theo thứ tự từ trái sang phải và chi phí để di chuyển từ một chữ sang chữ khác là khoảng cách giữa 2 chữ đó. Chi phí của văn bản là tổng các chi phí di chuyển giữa các chữ hay: \(\sum_{i=1}^{n - 1} | p_{s_{i + 1}} - p_{s_i} |\) với \(p_x\) là vị trí kí tự \(x\) từ trái sang phải của bàn phím.

Input

• Dòng đầu gồm 2 số \(n\) và \(m\).
• Dòng tiếp theo là xâu gồm \(n\) kí tự chứa \(m\) kí tự đầu tiên trong bảng chữ cái tiếng Anh.

Output

• In ra một số nguyên duy nhất là chi phí nhỏ nhất có thể.

Sample Test

Input:

6 3
aacabc

Output:

5

Giải thích:

• Sắp xếp thành bac

Ràng buộc

• Subtask 1: \(1 \le n \le 100, 1 \le m \le 10\) (40% số điểm).
• Subtask 2: \(1 \le n \le 100000, 1 \le m \le 10\) (30% số điểm).
• Subtask 3: \(1 \le n \le 100000, 1 \le m \le 20\) (30% số điểm).