Ở một nông trại nọ, có một chú bò biết nói tên là Jack. Jack vừa học được cách nói tiếng người, nhưng lại hay có tật... nói ngược. Cụ thể, mỗi khi nghe ai đó nói một câu, Jack sẽ trả lời lại bằng cách đảo ngược thứ tự các từ trong câu đó.

Ngoài ra, Jack là một chú bò lịch sự - nên sẽ thêm dấu phẩy (,) và dấu chấm (.) khi cần.

Để giúp mọi người có thể hiểu được tiếng Jack, bạn cần phải viết một chương trình thực hiện đúng như vậy: nhập vào một xâu ký tự, và xuất ra xâu mới có thứ tự các từ được đảo ngược. Hơn nữa, bạn cần thêm dấu chấm hết câu, viết hoa ký tự đầu tiên, và ký tự sau dấu chấm; đồng thời giữ nguyên dấu chấm và dấu phẩy để thể hiện sự lịch sự của Jack.

Input

Một dòng duy nhất chứa chuỗi ký tự có độ dài ~S\ (|S|\le 10^5)~ gồm các từ phân cách bởi đúng một dấu cách.

Xâu chỉ chứa các ký tự in thường, dấu cách, dấu phẩy và dấu chấm. Sau dấu phẩy hoặc dấu chấm sẽ có một dấu cách. Không có dấu cách thừa ở đầu hoặc cuối câu.

Output

Một dòng chứa xâu có thứ tự các từ được đảo ngược, với quy cách như trên. Chú ý, không được để dấu cách thừa!

Sample Input 1

con bo ten la jack, dung.

Sample Output 1

Dung, jack la ten bo con.

Sample Input 2

jack. yeu. thien an

Sample Output 2

An thien. Yeu. Jack.

Notes

Sử dụng getline(cin, s) để nhập dữ liệu xâu đầu vào string s;.

"Ối dồi ôi, ối dồi ôi
Trình là gì mà là trình ai chấm?
Anh chỉ biết làm ba mẹ tự hào,
Xây căn nhà thật to ở một mình hai tấm..."

Trình ai chấm? Trình do bạn chấm. HIEUTHUBA có nhờ bạn chấm "trình" của anh ấy, bằng một tiêu chí được giới ăn-đờ-grao công nhận:

Bạn được cấp ~n~ số điểm của ~n~ show diễn mà HIEUTHUBA đã tham dự (đếm được, đếm được!). Show càng ít điểm thì càng tệ. Ta có công thức tính "trình" của một dãy liên tiếp các show diễn từ show thứ ~i~ tới show thứ ~j~ sẽ là:

"Trình" của một ca sĩ sẽ là phong độ tốt nhất của họ, hay nói cách khác, nó sẽ là giá trị Trình~(i,j)~ lớn nhất có thể, với ~1\le i \le j\le n~.

Yêu cầu: Hãy tính "Trình" của HIEUTHUBA.

Input

• Dòng thứ nhất chứa số nguyên ~n~ ~(1\le n\le 10^6)~ chỉ số show diễn của HIEUTHUBA;

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(1\le a_i \le 10^9)~ – là điểm của từng show diễn tương ứng.

Output

• Một dòng chứa một số nguyên dương là "Trình" của HIEUTHUBA.

Scoring

• Subtask 1 (30%): ~n \le 300~.
• Subtask 2 (30%): ~n \le 3000~.
• Subtask 3 (20%): ~n \le 10^5~.
• Subtask 4 (20%): Không có ràng buộc gì thêm.

Sample Input 1

3
1 2 3

Sample Output 1

4

Notes

Để chắc chắn AC, các bạn sẽ cần ios_base::sync_with_stdio(false); cin.tie(nullptr).

Ở test ví dụ, ta lấy dãy show ~[2,3]~. Dãy này có độ dài ~2~, điểm của show tệ nhất là ~2~, nên có "Trình" là ~2\times 2 = 4~. Dãy này có "Trình" tốt nhất.

Loli cần bố trí các nhóm học sinh vào các phòng học. Có ~N~ nhóm học sinh được đánh số từ ~1~ tới ~N~. Có ~M~ phòng học được đánh số từ ~1~ tới ~M~.

Người ta sắp xếp các nhóm học sinh vào các phòng học theo quy tắc sau: Nếu nhóm học sinh thứ ~i~ được bố trí vào phòng học có số hiệu ~u~, nhóm học sinh thứ ~j~ được bố trí vào phòng học có số hiệu ~v~, mà có ~i<j~ thì phải có ~u<v~. </p>

Với mỗi phòng có nhận học sinh, các ghế thừa phải được chuyển ra hết, nếu thiếu ghế thì phải lấy từ kho vào cho đủ mỗi học sinh một ghế. Hãy chọn phương án bố trí sao cho tổng số lần phải chuyển ghế ra và chuyển ghế vào các phòng là ít nhất.

Input

• Dòng 1: Hai số nguyên dương ~N, M~ ~(N \le 2000, M \le 2000, N \le M)~;

• Dòng 2: ~N~ số nguyên dương ~a_i~ là số học sinh của nhóm thứ ~i~ ~(a_i < 10^5)~;

• Dòng 3: ~M~ số nguyên dương ~b_j~ là số ghế của phòng thứ ~j~ ~(b_j < 10^5)~.

Output

• Dòng 1: Ghi số lượng ghế ít nhất cần di chuyển vào, ra các phòng.

• Dòng 2: Số hiệu của nhóm học sinh thứ ~i~ được xếp vào phòng thứ ~j~.

Scoring

• Nếu chỉ in đúng số lượng ghế ít nhất cần di chuyển, bạn sẽ được ~30\%~ số điểm test đó.

• Subtask 1: ~30\%~ số điểm có ~N, M \le 10~.

• Subtask 2: ~40\%~ số điểm có ~N, M \le 100~.

• Subtask 3: ~30\%~ số điểm còn lại không có ràng buộc gì thêm.

Sample Input 1

3 5
5 6 9
2 9 17 6 2

Sample Output 1

9
1 2 4

Sample Input 2

3 5
15 6 11
2 9 17 6 2

Sample Output 2

11
3 4 5

Notes

Ở test đầu tiên, ta có phương án tối ưu là ~9~ vì:

• Bố trí nhóm thứ ~1~ với ~5~ học sinh vào phòng thứ ~1~ với ~2~ ghế. Số ghế cần lấy thêm là ~5-2 = 3~ ghế.

• Bố trí nhóm thứ ~2~ với ~6~ học sinh vào phòng thứ ~2~ với ~9~ ghế. Số ghế cần chuyển ra là ~9-6 = 3~ ghế.

• Bố trí nhóm thứ ~3~ với ~9~ học sinh vào phòng thứ ~4~ với ~6~ ghế. Số ghế cần lấy thêm là ~9-6 = 3~ ghế.

• Tổng cộng, cần ~3+3+3 = 9~ lượt chuyển ghế vào và ra.

Loli là một học sinh bình thường ở "Trường THPT Bình Thường". Về phần học hành, có lúc Loli try hard, có lúc lại chill chill, làm những thứ thỏa mãn đam mê. Loli đã học ở trường này ~n~ tuần. Mỗi tuần đều có một bài kiểm tra; Điểm kiểm tra của Loli tại tuần thứ ~i~ là một số nguyên không âm ~a_i~.

Loli muốn phân tích "phong độ" của mình tại những khoảng thời gian khác nhau. Ta định nghĩa khoảng thời gian ~[L;R]~ bắt đầu từ tuần thứ ~L~ và kết thúc ở tuần thứ ~R~. Loli xác định liệu phong độ trong khoảng thời gian ~[L;R]~ có phập phù hay không bằng ~P~, được tính như sau:

1. Viết ra toàn bộ điểm từ tuần thứ ~L~ tới tuần thứ ~R~, sau đó sắp xếp dãy đó theo thứ tự tăng dần. Gọi dãy điểm đó là ~S~.

2. Tính tổng ~P = (S_2 - S_1)^2 + (S_3 - S_2)^2 + \dots + (S_{R-L+1} - S_{R-L})^2~.

Yêu cầu: Cho dãy điểm của Loli và những khoảng thời gian cần phân tích, hãy xác định ~P~ của mỗi khoảng thời gian.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, m~ ~(1\le n, m \le 5\times 10^4)~;

• Dòng tiếp theo chứa ~n~ số nguyên ~a_i~ ~(0\le a_i \le 10^6)~;

• ~m~ dòng còn lại, mỗi dòng chứa khoảng thời gian có dạng ~L\ R~ ~(1 \le L \le R \le n)~.

Output

Gồm ~m~ dòng, dòng ~j~ chứa kết quả tương ứng của khoảng thời gian ~j~.

Scoring

• Subtask 1 (20%): ~n, m\le 200~.

• Subtask 2 (20%): ~n, m\le 5\times10^3~.

• Subtask 3 (20%): ~0\le a_i \le 100~.

• Subtask 4 (40%): Không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

3
5
4
2
0

Notes

Trong ví dụ trên:

• Với khoảng thời gian ~[1,4]~: Dãy ~S = [1,2,3,4]~, nên ta có ~P = (2-1)^2 + (3-2)^2 + (4-3)^2 = 3~.

• Với khoảng thời gian ~[3,5]~: Dãy ~S = [2,4,5]~, nên ta có ~P = (4-2)^2 + (5-4)^2 = 5~.

Loli là một nhân viên của tập đoàn khét tiếng Anh Em Rọt. Mặc dù công ty có lợi nhuận hàng chục tỷ một tháng, nhưng do ăn chia không đồng đều, nên ác cảm của Loli đối với công ty càng ngày càng ác liệt. Để trả mối tư thù, Loli quyết định sẽ tố cáo công ty bán thực phẩm chức năng giả!

Mặt hàng bán chạy nhất của công ty chính là Kẹo rau Kehahaha. Để lật tẩy trò lừa đảo này, trước hết Loli sẽ cần những tài liệu liên quan tới sản phẩm trên. Qua tìm hiểu, Loli biết được tài liệu này đã được mã hóa bằng một con số đặc biệt, đó là Số số nguyên dương thỏa mãn điều kiện sau:

• Số nguyên dương này dài không quá ~n~ chữ số;

• Số này không có chữ số ~0~ ở đầu;

• Chữ số thứ ~i\ (0\le i\le 9)~ phải xuất hiện ít nhất ~a_i~ lần.

Vì số lượng có thể rất lớn, dãy số cuối cùng sẽ là phần dư của kết quả khi chia cho ~10^9+7~. Như vậy, để giải mã, Loli cần biết chính xác số lượng số thỏa mãn điều kiện trên. Bạn hãy giúp Loli nhé!

Input

• Dòng đầu chứa số nguyên ~n\ (1\le n \le 100)~;

• Dòng thứ hai chứa ~10~ số nguyên ~a_i\ (0\le a_i\le n)~, ứng với các chữ số từ ~0~ đến ~9~.

Output

Một dòng chứa một số nguyên là phần dư kết quả khi chia cho ~10^9+7~.

Scoring

• Subtask 1 (40%): ~n\le 6~;

• Subtask 2 (40%): ~a_i \le 1~;

• Subtask 3 (20%): Không có ràng buộc gì thêm.

Sample Input 1

2
0 1 0 0 0 0 0 0 0 0

Sample Output 1

19

Sample Input 2

3
1 0 0 0 0 1 0 0 0 0

Sample Output 2

36

Notes

Ở ví dụ thứ nhất, dễ thấy chỉ có 19 số thỏa mãn, đó là số ~1~, các số từ ~10~ tới ~19~, và ~21~, ~31~, ..., ~91~.