Anh nông dân John có \(N\) con bò, mỗi con bò có một mã định danh khác nhau được viết dưới dạng chuỗi bit (chuỗi được tạo thành từ 2 loại kí tự '0' và '1'). Bessie là cô bò lớn tuổi nhất, cô nhớ mã định danh của tất cả con bò khác và thích đi lại trong trang trại để hỏi về mã định danh của chúng.

Khi một con bò được hỏi về mã định danh, nó sẽ bắt đầu trả lời chuỗi bit định danh của mình, tuy nhiên nó có thể quên phần sau của chuỗi và dừng lại trước khi trả lời đủ mã định danh của mình. Mỗi khi Bessie nghe được một chuỗi bit, nếu đó không phải là mã định danh của bất kỳ con bò nào trên trang trại, thì cô ấy sẽ nhún vai và đi khỏi. Tuy nhiên, nếu đó vô tình là mã định danh của một con bò khác mà không phải con bò cô ấy đang hỏi, thì cô ấy sẽ cho rằng đã xảy ra hành vi đánh cắp danh tính và đưa trang trại vào tình trạng phong tỏa. Lưu ý rằng điều này có thể xảy ra ngay cả khi con bò nói đầy đủ mã định danh của nó.

John cảm thấy mệt mỏi vì tình trạng này nên muốn ngăn chặn nó xảy ra. Anh sẵn sàng thay đổi mã định danh của các con bò bằng cách thêm một số bit vào đó. Trong một giây, anh có thể thêm một bit vào cuối mã định danh của bất kỳ con bò nào. Hãy tính toán thời gian ít nhất để anh ngăn chặn được việc phong tỏa trang trại.

Input

• Dòng đầu tiên chứa \(N\), là số lượng con bò trên trang trại của nông dân John.
• \(N\) dòng tiếp theo, dòng thứ \(k\) chứa một chuỗi bit là mã định danh của con bò thứ \(k\).
• Dữ liệu đảm bảo không có mã định danh nào là chuỗi rỗng và tổng dộ dài của tất cả mã định danh không quá \(10^6\).

Output

• Gồm một số tự nhiên duy nhất là số giây tối thiểu mà John cần dành ra để đảm bảo rằng việc phong tỏa sẽ không bao giờ xảy ra.

Scoring

• Subtask \(1\): Tất cả các mã định danh có độ dài chính xác là \(1\).
• Subtask \(2\): \(N \leq 10^2\) và tổng độ dài của các mã định danh không vượt quá \(10^3\).
• Subtask \(3\): Không có ràng buộc gì thêm.

Example

3
1
1
1

5

3
1
11
111

2

3
1
1
11

4

5
0
01
0011
010
01

6

14
0
1
1
0
1
0
1
1
1
1
1
0
0
1

41

Nông dân John muốn chia đều cỏ giữa hai con bò yêu thích của mình là Bessie và Elsie. Anh có \(N\) (\(1 \leq N \leq 2 \times 10^5\)) bó cỏ được sắp xếp theo thứ tự không tăng dần, trong đó bó cỏ thứ \(i\) có \(a_i\) cọng cỏ (\(2 \times 10^5 \geq a_1 \geq a_2 \geq ... \geq a_N \geq1\)).

Nông dân John đang nghĩ đến chuyện chia những bó cỏ một cách lần lượt cho hai con bò, cụ thể như sau:

• Nông dân John chia các bó cỏ theo đúng thứ tự từ \(l\) đến \(r\) trong kho cỏ cho trước.
• Với bó cỏ thứ \(i\), anh John sẽ đưa cho con bò có ít cỏ hơn. Nếu 2 con bò cố lượng cỏ bằng nhau, anh John sẽ đưa cho Bessie.

Bạn được cho Q truy vấn (\(1 \leq Q \leq 2 \times 10^5\)), mỗi truy vấn gồm 3 số nguyên \(l, r, x\) (\(1 \leq l \leq r \leq N, |x| \leq 10^9\)). Với mỗi truy vấn, bạn cần tìm xem Bessie sẽ có nhiều hơn Elsie bao nhiêu cọng cỏ, biết Bessie ban đầu có nhiều hơn Elsie \(x\) cọng cỏ. Lưu ý rằng giá trị này âm nếu Elsie có nhiều cỏ hơn Bessie.

Input

• Dòng đầu tiên chứa \(N\).
• Dòng thứ hai chứa \(a_1…a_N\).
• Dòng thứ ba chứa \(Q\).
• \(Q\) dòng tiếp theo chứa \(l, r, x\).

Output

• Gồm \(Q\) dòng, mỗi dòng chứa câu trả lời cho mỗi truy vấn.

Scoring

• Subtask \(1\): \(Q \leq 100\)
• Subtask \(2\): Tối đa \(100\) giá trị \(a_i\) khác nhau
• Subtask \(3\): Không có ràng buộc gì thêm.

Example

2
3 1
15
1 1 -2
1 1 -1
1 1 0
1 1 1
1 1 2
1 2 -2
1 2 -1
1 2 0
1 2 1
1 2 2
2 2 -2
2 2 -1
2 2 0
2 2 1
2 2 2

1
2
3
-2
-1
0
1
2
-1
0
-1
0
1
0
1

5
4 4 3 1 1
7
1 1 20
1 2 20
1 5 20
1 1 0
1 5 0
1 4 0
3 5 2

16
12
7
4
1
2
1

Bạn và một robot ban đầu đứng tại điểm \(0\) trên một vòng tròn có chu vi \(L\) (\(1 \leq L \leq 10^9\)). Bạn có thể di chuyển liên tục theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ trên vòng tròn với tốc độ \(1\) đơn vị trên giây. Tất cả các chuyển động trong bài toán này là liên tục.

Mục tiêu của bạn là đặt thêm \(R-1\) robot sao cho đến cuối cùng, mọi cặp robot liền kề cách nhau \(L/R\) đơn vị (\(2 \leq R \leq 20\), \(R\) chia hết cho \(L\)). Có \(N\) (\(1 \leq N \leq 10^5\)) điểm kích hoạt, điểm thứ \(i\) cách điểm \(0\) một khoảng \(a_i\) theo chiều ngược kim đồng hồ (\(0 < a_i < L\)). Nếu bạn đang ở tại một điểm kích hoạt, bạn có thể đặt một robot tại đó. Tất cả các robot (kể cả robot ban đầu) di chuyển ngược chiều kim đồng hồ liên tục với tốc độ \(1\) đơn vị trên \(K\) giây (\(1 \leq K \leq 10^9\)).

Hãy tính toán thời gian tối thiểu cần thiết để đạt được mục tiêu.

Input

• Dòng đầu tiên chứa \(L\), \(R\), \(N\), và \(K\).
• Dòng tiếp theo chứa \(N\) số nguyên \(a_1, a_2, ..., a_N\) cách nhau bởi dấu cách.

Output

• Gồm một số duy nhất là thời gian ngắn nhất để đạt được mục tiêu đặt ra.

Scoring

• Subtask \(1\): Tất cả các mã định danh có độ dài chính xác là \(1\).
• Subtask \(2\): \(N \leq 10^2\) và tổng độ dài của các mã định danh không vượt quá \(10^3\).
• Subtask \(3\): Không có ràng buộc gì thêm.

Example

10 2 1 2
6

22

10 2 1 2
7

4

32 4 5 2
0 23 12 5 11

48

24 3 1 2
16

48