Thống kê là một học phần quan trọng trong chương trình học đại học tại Việt Nam, là nền tảng cho nhiều lĩnh vực nghiên cứu và ứng dụng khác nhau. Trong môn học này, sinh viên sẽ được giới thiệu về các phương pháp và công cụ thống kê cơ bản để phân tích dữ liệu và rút ra những kết luận có ý nghĩa từ chúng. Không chỉ là một môn học lý thuyết, thống kê cũng đòi hỏi sinh viên thực hành thông qua việc áp dụng các phương pháp thống kê vào các bài toán thực tế. Môn thống kê không chỉ giúp sinh viên hiểu rõ hơn về các phương pháp nghiên cứu khoa học mà còn cung cấp cho họ kỹ năng quan trọng để trở thành những nhà phân tích dữ liệu thành công trong lĩnh vực nghiên cứu và doanh nghiệp.

Để thực hành thống kê, Đại đã lấy ra một mẫu ngẫu nhiên gồm \(n\) mục dữ liệu. Trong tiết học thực hành đầu tiên, mỗi sinh viên cần lập trình tính toán được những thông số sau:

• Giá trị lớn nhất, gọi là \(\max\)
• Giá trị nhỏ nhất, gọi là \(\min\)
• Giá trị trung bình, là \(\texttt{avg}\) (kí hiệu toán chuẩn: \(\mu\))
• Giá trị trung vị \(\texttt{median}\): được định nghĩa là giá trị nằm giữa trong một dãy số đã sắp xếp. Trong trường hợp \(n\) chẵn thì lấy giá trị ở bên phải trong hai giá trị ở giữa.
• Mode của tập hợp \(\texttt{mode}\) là giá trị xuất hiện nhiều nhất trong mẫu.
• Độ lệch chuẩn \(\sigma\) (\(\texttt{sigma}\), phiên âm là xích-ma): Được tính theo công thức: \(\sigma = \sqrt{\frac{\sum_i^n{(x_i - \mu)^2}}{n}}\).

Yêu cầu: Cho trước \(n\) và \(n\) số của dãy \(a\) tương ứng với dữ liệu. Hãy tính toán các thông số trên và in ra trên từng dòng

Chú thích (dành cho học sinh): Hãy hình dung kí hiệu \(\sum_i^{n} a_i\) là for (i chạy từ 1 tới n) tổng += a[i]

Input

• Dòng đầu tiên chứa số nguyên dương \(n (1\le n\le 10^4)\)
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n (|a_i| \le 10^9)\)

Output

Gồm chính xác \(6\) dòng chứa các thông số tính được theo định dạng như sau:

max
min
avg
median
mode
sigma

Scoring

Đáp án in ra không được sai khác trong vòng 6 chữ số sau dấu thập phân.
Điểm được chia đều trên mỗi test. Với mỗi thông số bạn tính được đúng với của BTC, bạn được điểm thành phần như sau:

• \(\texttt{max}\): \(7.5\%\) số điểm của test
• \(\texttt{min}\): \(7.5\%\) số điểm của test
• \(\texttt{avg}\): \(20\%\) số điểm của test
• \(\texttt{median}\): \(20\%\) số điểm của test
• \(\texttt{mode}\): \(20\%\) số điểm của test
• \(\texttt{sigma}\): \(25\%\) số điểm của test

Lưu ý, đối với \(\texttt{mode}\), nếu có nhiều giá trị cùng xuất hiện nhiều lần nhất thì có thể in giá trị bất kì.

Example

10
7 9 2 3 6 5 1 8 100 -5

100
-5
13.600000000000
6
-5
29.059249818259

Quỳnh chơi một trò chơi như sau. Ban đầu chọn ra hai số tự nhiên \(a,b\). Tại mỗi bước, Quỳnh viết số lớn hơn trong hai số \(a,b\) lên bảng, rồi trừ nó đi một lượng bằng với số nhỏ hơn (nếu tại một thời điểm nào đó \(a = b\), Quỳnh lấy một số bất kì trừ vào số còn lại). Quỳnh dừng lại khi một trong hai số bằng \(0\). Hỏi sau khi dừng lại, tổng các số được viết trên bảng là bao nhiêu?

Hãy đưa ra đáp án sau khi chia lấy dư cho \(998244353\)

Input

• Gồm một dòng duy nhất chứa hai số nguyên dương \(a,b (1\le a,b\le 10^{18})\)

Output

• Gồm một dòng duy nhất chứa tổng cần tính, theo modulo \(998244353\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(a,b \le 10^4\)
• Subtask \(2\) (\(20\%\) số điểm): \(a,b \le 10^9\)
• Subtask \(3\) (\(20\%\) số điểm): \(a\) chia hết cho \(b\).
• Subtask \(4\) (\(30\%\) số điểm): không có ràng buộc gì thêm

Example

98 12

490

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

Thuận rất thích chơi game, tuy nhiên hôm nay Thuận phải học toán. Vì thế, cậu ấy đã nghiên cứu một trò chơi toán học rất thú vị như sau. Xét băng giấy dài, thẳng gồm \(n\) ô vuông liên tiếp. Bắt đầu từ ô số \(1\), cậu sẽ lần lượt "nhảy" tới ô số \(n\) theo các quy tắc đã định sẵn.
Cậu đặt ra \(k\) quy tắc, mỗi quy tắc gồm một đoạn số \([l, r]\), tức là với mỗi số \(d\) mà \(l \le d \le r\), thì Thuận sẽ được phép nhảy từ ô số \(i\) sang ô số \(i+d\) (tất nhiên \(i+d \le n\)).
Là một cậu bé thông minh và có lòng hiếu kì khám phá những kiến thức mới lạ, Thuận đã thử liệt kê tất cả các cách khác nhau để "nhảy" từ ô \(1\) tới ô \(n\) theo những quy tắc trên, nhưng cậu không biết mình đã đếm đủ chưa. Do đó, Thuận cần các bạn lập trình để tính xem có bao nhiêu cách để nhảy từ ô số \(1\) tới ô số \(n\).
Để thuận tiện, Thuận đã xác định cách thức sau để phân biệt hai cách nhảy khác nhau bất kì từ ô \(1\) tới ô \(n\): Mỗi khi đứng tại một ô nào mới, Thuận sẽ viết thêm số hiệu của ô đó vào cuối dãy số. Dãy số thu được sau mỗi lần đi tới \(n\) sẽ đặc trưng cho một cách nhảy riêng biệt.
Ví dụ, với \(n = 4\), \(k = 1\) và \(l_1 = 1, r_1 = 2\), có thể tồn tại những cách nhảy sau:

• \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\)
• \(1 \rightarrow 3 \rightarrow 4\)
• \(1 \rightarrow 2 \rightarrow 4\)

Lưu ý, vì kết quả có thể rất lớn nên hãy in ra phần dư của nó sau khi chia cho \(10^9 + 7\)

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) \((1 \leq n \le 5 \times 10^{5}, 1 \le k \le 50)\).
• \(k\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i, r_i (1 \le l_i \le r_i \le n)\) biểu thị cho một quy tắc

Output

• Gồm một dòng duy nhất chứa số cách đếm được, khi chia lấy dư cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(16\%\) số điểm): \(n \le 5000, k = 1\).
• Subtask \(2\) (\(16\%\) số điểm): \(n \le 5000, k = 2\).
• Subtask \(3\) (\(18\%\) số điểm): \(n \le 5000\).
• Subtask \(4\) (\(16\%\) số điểm): \(k = 1\)
• Subtask \(5\) (\(16\%\) số điểm): với \(i \neq j\) bất kì, luôn có \(\min(r_i, r_j) < \max(l_i, l_j)\)
• Subtask \(6\) (\(18\%\) số điểm): không có ràng buộc gì thêm.

Example

7 1
2 4

4