Trong lễ hội xuân ở quảng trường Võ Nguyên Giáp, một thùng phiếu có A viên bi đỏ và B viên bi xanh. Nếu rút ngẫu nhiên 1 viên, xác suất rút được bi đỏ là phân số A / (A + B). Hãy in ra xác suất này dưới dạng một số nguyên modulo 998244353 (một mô đun thường dùng trong các bài toán xác suất lập trình thi đấu).

Dữ liệu vào: Hai số nguyên dương A và B.

Kết quả ra: Giá trị của A * nghịch đảo(A + B) modulo 998244353.

Ràng buộc: 1 <= A, B <= 10^6.

Ví dụ:

Input:

1 1

Output:

499122177

Nhà máy dầu ~A~ vừa mời một kỹ sư ~E~ đến lắp đặt một dàn máy bơm dầu tự động hiện đại bậc nhất Đông Nam Á. Trên băng chuyền có ~n~ thùng dầu rỗng, được đánh số từ ~1~ đến ~n~. Mỗi giây, một đầu bơm sẽ thực hiện bơm dầu vào một đoạn liên tiếp các thùng, từ thùng dầu thứ i đến thùng dầu thứ j ~(1 ≤ i ≤ j ≤ n)~, mỗi thùng trong đoạn này sẽ được bơm thêm ~k~ lít dầu.

Sau ~m~ giây bơm, hãy xác định lượng dầu có trong từng thùng.

Dữ liệu vào:

Dòng đầu tiên chứa một số nguyên t — số lượng test case.

Với mỗi test case:

Dòng đầu tiên chứa hai số nguyên n và m — số thùng dầu và số giây bơm.

Tiếp theo là m dòng, mỗi dòng chứa ba số nguyên i, j, k, nghĩa là trong giây này, máy bơm sẽ bơm thêm k lít dầu vào tất cả các thùng từ i đến j.

Dữ liệu ra:

Với mỗi test case, in ra một dòng gồm ~n~ số nguyên, trong đó số thứ ~x~ là lượng dầu có trong thùng dầu thứ ~x~ sau khi thực hiện xong tất cả các lần bơm.

Ví dụ :

Input:

1
3 1
1 3 5

Output:

5 5 5

Tuyến đường ven biển của thành phố Highland có N chiếc đèn. Không may cơn bão vừa rồi đã làm hỏng B chiếc đèn. Để khắc phục sự cố và nhanh chóng khôi phục lại hoạt động du lịch, chính quyền thành phố đã quyết định sửa tạm thời một số đèn đường bị hỏng sao cho có ít nhất một khu vực có K chiếc đèn liên tiếp hoạt động. Các bạn hãy xác định xem số đèn đường cần phải sữa chữa ít nhất là bao nhiêu?

Đầu vào:

• Dòng đầu tiên gồm 3 số nguyên dương N, K và B (1 ≤ B, K ≤ N ≤ 100 000).
• B dòng tiếp theo, mỗi dòng chứa vị trí của một chiếc đèn bị hỏng.

Đầu ra: In ra số đèn đường cần sửa ít nhất sao cho có một khu vực có nhiều hơn hoặc bằng K chiếc đèn hoạt động.

Input:

10 6 5
2
10
1
5
9

Output:

1

Có N chiếc xe điện VinFast cần vào trạm sạc. Chiếc thứ i đến vào thời điểm Ai và rời đi vào thời điểm Di. Nếu 2 xe có thời gian sạc trùng nhau (kể cả tại mốc thời gian đến/đi), chúng phải dùng 2 trụ sạc khác nhau. Hỏi trạm cần trang bị ít nhất bao nhiêu trụ sạc để không xe nào phải chờ?

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

N dòng tiếp theo: Mỗi dòng chứa 2 số nguyên Ai và Di (0 <= Ai <= Di <= 2359, định dạng HHMM).

Kết quả ra: Số trụ sạc tối thiểu.

Ví dụ:

Input:

3
900 930
915 1200
930 1100

Output:

3

(Tại thời điểm 930 có 3 xe cùng ở trạm).