Ôn tập

Cho số nguyên dương \(N\). Tính tổng:
\(\sum\limits_{i = 1}^N {\frac{N \times i + i}{i}}\)

Input

• Dòng đầu ghi \(Q\) không quá \(100\) - số câu hỏi.
• \(Q\) dòng tiếp theo, mỗi dòng ghi số nguyên dương \(N\) \((N \le 10^{21})\)

Output

• Ứng với mỗi câu hỏi, in ra đáp án cần tìm.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \le 10^5\).
• Subtask \(2\) (\(50\%\) số điểm): \(N \le 10^{13}\).
• Subtask \(3\) (\(10\%\) số điểm): \(N \le 10^{21}\).

Example

3
4
5
6

20
30
42

Thuận là chủ của thương hiệu Mountain Game - chuyên cung cấp dịch vụ leo núi dưới dạng một trò chơi thi đấu. Khu vực tổ chức thi leo núi của Mountain Game có thể được chia thành \(n\) cấp bậc với độ cao tăng dần. Trong đó, \(a_i\) là độ khó khăn để vượt từ cấp \(i-1\) lên cấp \(i\). Ta quy ước cấp \(0\) là mặt đất, nơi mỗi người chơi sẽ bắt đầu.
Theo luật chơi, nếu người chơi hiện đang có mức độ thể lực là \(x\), thì người đó chỉ vượt qua được những cấp bậc có độ khó không lớn hơn \(x\). Việc di chuyển lên các cấp không tiêu hao thể lực.
Sau khi đi tới cấp độ \(i\), bất kì người chơi nào cũng sẽ nhận được một buff hoặc nerf tương ứng, giúp thể lực của người đó giảm đi một lượng \(b_i\), tức là

(nếu \(b_i\) âm, tức thể lực của người chơi được tăng lên - buff). Ta giả sử có vô hạn buff / nerf tại mỗi cấp, nhưng mỗi người chơi khi tiến tới cấp \(i\) sẽ được nhận buff tại tầng đó một lần duy nhất.
Luật chơi cũng giới hạn người chơi di chuyển từ cấp thấp lên cấp cao hơn, lần lượt, tức từ cấp \(i\) lên cấp \(i+1\) theo thứ tự \(1,2,3,\dots,n\).
Ngoài ra, để đảm bảo an toàn, khi một người chơi không thể tiến thêm được nữa (không đủ thể lực hoặc đã ở cấp cuối cùng), trên mỗi cấp đã có bố trí sẵn phòng nghỉ ngơi và cánh cửa thần kì để mỗi người chơi dừng lại và trở về mà không tiêu hao thể lực.
Dĩ nhiên, khi vượt qua một màn với độ khó khăn là \(x\) thì người chơi cũng được thưởng thêm một lượng tiền là \(x\) USD. Phần thưởng này đã thu hút rất nhiều người chơi đăng ký.
Có \(q\) người chơi đã đăng ký Mountain Game, với mỗi người thứ \(j\), Thuận biết được thể lực của người đó là \(k_j\) (theo thông tin đăng ký). Để dự trù kinh phí, Thuận cần tính trước với mỗi người, tổng tiền thưởng cần chuẩn bị cho anh ta là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n,q \leq 5 \times 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n (1 \le a_i \le 10^9)\) là độ khó của các cấp độ.
• Dòng thứ ba chứa \(n\) số nguyên \(b_1, b_2, \dots, b_n (|b_i| \le 10^9)\) là mức độ thay đổi thể lực của từng cấp.
• \(q\) dòng tiếp theo, dòng thứ \(j\) chứa một số \(k_j\) \((1 \leq k_j \leq 10^{15})\) là thể lực của người chơi thứ \(j\).

Output

• Với mỗi người chơi, in ra lượng tiền tối đa của người đó có thể được thưởng, trên một dòng riêng biệt.

Scoring

• Subtask \(1\) (\(24\%\) số điểm): \(n,q \le 5000\).
• Subtask \(2\) (\(24\%\) số điểm): \(b_i = 0\).
• Subtask \(3\) (\(26\%\) số điểm): \(b_i < 0\).
• Subtask \(4\) (\(26\%\) số điểm): không có ràng buộc gì thêm.

Example

3 4
2 3 5
2 -1 1
1
2
5
8

0
2
5
10

Trong hội thi DH và ĐBBB 2017 có tổ chức cho các thí sinh trò chơi lắp ghép như sau: Cho \(K\) loại khối gỗ, mỗi khối gỗ không hạn chế số lượng và có chiều cao tương ứng là \(H_1, H_2, ..., H_k\), dùng các khối gỗ này sếp chồng lên nhau để đạt đúng độ cao \(N\). Mỗi thí sinh tham gia trò chơi là tìm số cách sắp xếp khác nhau từ các khối gỗ để đạt đúng độ cao \(N\).

Yêu cầu: Cho \(N\) và chiều cao của mỗi loại khối gỗ, tìm số cách xếp từ các khối gỗ để đạt độ cao \(N\).

Input

• Dòng 1 ghi 2 số nguyên dương \(N\) và \(K\).
• Dòng 2 ghi \(K\) số \(H_1, H_2, ..., H_k\), các số khác nhau từng đôi một.

Output

• Ghi ra một số nguyên là số cách xếp gỗ, vì số cách rất lớn nên lấy kết quả là phần dư của \(10^9+7\).

Constraints

• \(K\le N \le 10^5, K\le 1000\)
• \(0 < H_i \le N\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(K < N \le 10, 0 < H_i \le N\)
• Subtask \(2\) (\(30\%\) số điểm): \(N \le 10^4, K = 3\) và độ cao tương ứng là \(1, 2\) và \(3\), \(0 < H_i \le N\)
• Subtask \(3\) (\(40\%\) số điểm): \(N \le 10^5\), \(3 < K \le 1000\) và \(0 < H_i \le N\)

Example

3 2
1 2 

3