Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(1 \leq N,Q \leq 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): không có giới hạn gì thêm.

Example

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

3
2
1
1
0

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(1 \leq N \leq 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \leq N \leq 10^3\).
• Subtask \(3\) (\(30\%\) số điểm): không có giới hạn gì thêm.

Example

8 4 2
1 1 3 2 10 10 8 1 

15

Hiện tại ở vương quốc loài ếch đang tổ chức một cuộc thi. Cuộc thi như sau: có \(N\) cây cột, cây cột thứ \(i\) có chiều cao là \(h_i (1 \le i \le N)\). Chú ếch tham gia sẽ được chọn xuất phát ở một cây cột bất kỳ, tại mỗi thời điểm, chú ếch sẽ chỉ được chọn nhảy về phía bên phải và chỉ được nhảy đến những cây cột có chiều cao lớn hơn chiều cao của cây cột chú đang đứng, hay nói cách khác, giả sử chú ếch đang đứng ở cây cột thứ \(x\), chú ếch sẽ chỉ được nhảy tới cây cột thứ \(y\) gần nhất sao cho \(h_x < h_y\) và \(x < y\). Phần thi của chú ếch sẽ kết thúc nếu như chú không thể thực hiện được việc nhảy của mình nữa. Chú ếch thắng cuộc sẽ là chú ếch thực hiện được nhiều lần nhảy nhất.

Hoàng tử ếch cũng tham gia cuộc thi này, chú ấy đã đặt ra \(Q\) câu hỏi để tìm ra cây cột phù hợp để nhảy. Câu hỏi thứ \(i\) sẽ có dạng: \(x_i\) là số bước nhảy có thể thực hiện được nếu như chú chọn xuất phát ở cây cột thứ \(x_i\).

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N, Q (1 \le N, Q \le 10^ 5)\).
• Dòng thứ hai là gồm \(N\) số nguyên dương lần lượt là độ cao của các cây cột \((1 \le h_i \le 10^9)\).
• \(Q\) dòng tiếp theo, dòng thứ \(i\) gồm một số nguyên dương \(x _i (1 \le x_i \le N)\).

Output

• Gồm \(Q\) dòng, dòng thứ \(i\) trả lời cho câu hỏi thứ \(i\).

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(1 \le N, Q \le 10^3\) ,
• Subtask \(2\) (\(30\%\) số điểm): không có giới hạn gì thêm.

Example

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

3
2
1
1
0

Cho hàm tuyến tính \(f(x) = Ax + B\). Định nghĩa \(g_0(x) = x\) và \(g_n(x) = f(g_{n-1}(x))\) với \(n \ge 1\). Cho trước các số \(A, B, n, x\). Hãy tính \(g_n(x)\) mod cho \(10^9+7\)

Input

Đọc từ file văn bản HAMSO.INP

• Một dòng duy nhất gồm các số \(A, B, n, x (1 \le A, B, x \le 10^9, 1 \le n \le 10^{18})\)

Output

• Một dòng duy nhất là đáp án

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(1 \le A, B, x \le 10^6, 1 \le n \le 10^6\)
• Subtask \(2\) (\(60\%\) số điểm): \(1 \le A, B, x \le 10^9, 1 \le n \le 10^{18}\)

Example

3 4 1 1

7

Sau khi chiến thắng quân xâm lược, nhà vua của đất nước Islanders muốn xây dựng hệ thống doanh trại quân sự tại các ngôi làng để củng cố vững chắc nền độc lập của mình. Đất
nước có \(n\) ngôi làng được đánh số từ \(1\) đến \(n\) và các ngôi làng này được nối với nhau bởi hệ
thống giao thông gồm \(m\) tuyến đường hai chiều, mỗi tuyến đường nối trực tiếp một cặp ngôi
làng, đảm bảo luôn có đường đi lại giữa hai ngôi làng bất kì trong nước (trực tiếp hoặc đi
qua một số ngôi làng khác). Giữa hai ngôi làng bất kì không có quá một tuyến đường nối
trực tiếp. Nhà vua có tổng cộng \(b\) kho lương thực được đặt trên khắp cả nước, mỗi kho nằm
ở một ngôi làng khác nhau. Sau khi họp với các tướng lĩnh, nhà vua đã chọn ra \(r\) ngôi làng
khác nhau để đặt doanh trại quân sự.
Yêu cầu với mỗi ngôi làng được đặt doanh trại quân sự, nhiệm vụ của bạn là tính toán số
tuyến đường ít nhất cần đi nếu xuất phát từ ngôi làng đó đến một kho lương thực bất kì.

Input

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

• Dòng thứ nhất gồm bốn số nguyên: \(n, m, b, r(2 \le n \le 5.10^5;1 \le m \le 5.10^5;1 \le b, r \le n)\).
• Dòng thứ hai gồm \(b\) số nguyên là chỉ số của các ngôi làng được đặt kho lương.
• Dòng thứ ba gồm \(r\) số nguyên là chỉ số của các ngôi làng được đặt doanh trại.
• \(m\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u\) và \(v\) thể hiện có một tuyến đường
  hai chiều nối trực tiếp hai ngôi làng \(u\) và \(v\).

Output

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

• In ra \(r\) số nguyên trên cùng một dòng là kết quả tính được của các ngôi làng được đặt
  doanh trại quân sự theo thứ tự của dữ liệu vào.

Scoring

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

Example

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

1 2 1

Bạn được giao nhiệm vụ như sau: Cho một dãy số \(A\) bao gồm \(N\) số nguyên, yêu cầu hãy
chia dãy số trên thành hai phần liên tiếp sao cho tổng các số ở phần bên trái bằng tổng các
số ở phần bên phải. Với mỗi lần như vậy bạn sẽ được 1 điểm, còn nếu không thể chia được
thì nhiệm vụ sẽ kết thúc. Sau khi chia thành công, bạn sẽ tiếp tục được chọn dãy số bên trái
hoặc bên phải để tiếp tục nhiệm vụ với các bước như trên cho đến khi kết thúc. Hãy tính
xem số điểm lớn nhất bạn có thể đạt được là bao nhiêu?

Input

Đọc từ file văn bản CHIADAY.INP:

• Dòng đầu tiên ghi một số nguyên \(T (1 \le T \le 10)\) là số lượng bộ dữ liệu. Mỗi
  bộ liệu bao gồm hai dòng:
• Dòng đầu tiên ghi một số nguyên \(N\) là số lượng phần tử của dãy \(A\).
• Dòng thứ hai gồm Nphần tử của dãy \(A\) được ghi cách nhau bởi dấu cách \((0 \le a_i \le 10^9)\).

Output

Ghi ra file văn bản CHIADAY.OUT

• Với mỗi bộ dữ liệu in ra một số nguyên trên một dòng là kết quả của bộ dữ liệu đó.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \le 200\).
• Subtask \(2\) (\(60\%\) số điểm): \(N \le 2000\).
• Subtask \(3\) (\(10\%\) số điểm): \(N \le 20000\).

Example

3
3
3 3 3
4
2 2 2 2
7
4 1 0 1 1 0 1

0
2
3

Input

10 3 4 10
8 1 4 2

Output

44

Input

4 3
2 5 9 7
35 74 13

Output

0 8
0 4
1 6

Hùng nổi tiếng trong lớp là một người gọn gàng, ngăn nắp. Đồ đạc trong phòng của Hùng cũng được phân loại, sắp xếp có trật tự. Chính vì vậy, khi làm các bài tập số học, Hùng rất không hài lòng nếu gặp các số mà các chữ số không theo một trình tự nào, lúc tăng lúc giảm. Hùng chỉ thích các số có các chữ số xuất hiện theo trình tự không giảm, ví dụ \(1111, 123, 88999, . . .\) và gọi đó là những số dễ chịu.
Hùng cũng hiểu rằng trong cuộc sống những điều dễ chịu không nhiều và trong thế giới số cũng vậy! Để kiểm tra, so sánh xem thế giới thực và thế giới số nơi nào tỷ lệ điều dễ chịu cao hơn Hùng bắt tay vào việc tính số dễ chịu xuất hiện trong đoạn \([a, b]\). Cho 2 số nguyên \(a\) và \(b (0 < a \le b \le 10^{100})\). Hãy xác định số lượng số dễ chịu trong đoạn \([a, b]\). Kết quả có thể rất lớn vì vậy chỉ cần đưa ra theo mô đun \(10^9+7\).

Input

Vào từ file văn bản PLEASANT.INP có cấu trúc:

• Dòng đầu tiên chứa số nguyên \(a\);
• Dòng thứ 2 chứa số nguyên \(b\).

Output

• Đưa ra file văn bản PLEASANT.OUT một số nguyên: số lượng số dễ chịu tìm
  được theo mô đun \(10^9+7\).

Example

1
100

54

Xét bảng hình chữ nhật kích thước \(m \times n\) ô. Các hàng được đánh số từ \(1\) đến \(m\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) từ trái qua phải. Ô nằm trên hàng \(i\) và cột \(j\) được ghi một số nguyên không âm ký hiệu \(c_{ij}\) .Ở góc trên trái bảng có một quân cờ. Ta phải chuyển quân cờ về ô dưới phải của bảng theo quy tắc sau:

• Tại mỗi bước nhảy, chỉ được di chuyển sang phải trên cùng một hàng hoặc di chuyển xuống dưới theo cùng một cột
• Kích thước bước nhảy không được vượt quá số ghi trên ô có quân cờ hiện tại
• Chỉ được di chuyển trong phạm vi bảng đang xét

Kích thước của bước nhảy từ ô \((i,j)\) tới ô \((u, v)\) được tính bằng giá trị \(u + v − i − j\).

Yêu cầu: Cho dãy \(a_1, a_2, ..., a_m, b_1, b_2,...,b_n\) và số nguyên dương \(k\). Bảng \(C\) kích thước \(m \times n\) được xác định với \(C_{ij} = 1 + [(a_i + b_j)\) mod \(k] \forall i = 1 ÷ m; j = 1 ÷ n\). Hãy tính số lượng cách di chuyển quân cờ từ ô trên trái \((1,1)\) xuống ô dưới phải \((m, n)\).

Input

vào từ file văn bản JUMP.INP có cấu trúc như sau:

• Dòng đầu chứa 3 số nguyên dương \(m, n, k ( m, n, k \le 4.10^3)\)
• Dòng thứ hai chứa \(m\) số nguyên \(a_1, a_2, a_3, ... , a_m (0 \le a_i \le 10^9)\)
• Dòng thứ ba chứa \(n\) số nguyên \(b_1, b_2, b_3, ... , b_n (0 \le b_i \le 10^9)\)

Output

• Ghi ra file văn bản JUMP.OUT một số nguyên duy nhất là số cách di chuyển tìm
  được lấy theo module \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(m, n \le 10, k = 1\)
• Subtask \(2\) (\(15\%\) số điểm): \(m, n \le 10^3, k = 1\)
• Subtask \(3\) (\(20\%\) số điểm): \(m, n \le 10^3, k \le 10\)
• Subtask \(4\) (\(20\%\) số điểm): \(m, n \le 10^3\)
• Subtask \(5\) (\(30\%\) số điểm): không có ràng buộc gì thêm

Example

3 2 1
3 4 11
2 5

3

3 2 2
3 4 11
2 5

4

Cho số tự nhiên n và tập \(M=\{S_1, S_2, ..., S_n\}\) gồm nhiều xâu không rỗng: \(S_k (1\le k\le n)\)
chỉ gồm các ký tự thuộc tập {‘a’,’b’}. Ký hiệu \(|S_k|\) là số ký tự của \(S_k\) nghĩa là độ dài của \(S_k\).
Một xâu con \(S_k[i:j]\) của xâu Sk sẽ gồm các ký tự liên tiếp ở vị trí \(i, i+1, ...., j\) của \(S_k\). Do đó
nếu \(S_k\)=’abbbaababa’ thì \(S_k[3:6]\)=’bbaa’ được tô đậm trong \(S_k\) như sau: ’abbbaababa’

Yêu cầu: Cho tập \(M\), hãy tìm độ dài lớn nhất của xâu con có trong tất cả các xâu của \(M\).

Input

Vào từ file văn bản SUBSEC.INP có cấu trúc:

• Dòng đầu tiên là số tự nhiên \(n\);
• Mỗi dòng trong \(n\) dòng tiếp theo là một xâu của \(M\)

Output

• Đưa ra file văn bản SUBSEC.OUT là một số nguyên duy nhất - độ dài của xâu
  con tìm thấy.

Constants

• \(1 < n < 5\).
• Nếu \(|S| = |S_1| + |S_2| + ... + |S_n|\), thì \(|S| < 50 001\).
• Bảo đảm các test luôn có nghiệm.
• Bảo đảm một nghiệm không lớn hơn \(60\).

Example

4
abbabaaaaabb
aaaababab
bbbbaaaab
aaaaaaabaaab

5