Sau một cuộc phiêu lưu đầy kịch tính qua 8 vòng loại đầy thách thức, Huy đã đặt bước chân tới rương kho báu huyền bí mà anh ta luôn ao ước. Nhưng để mở khóa kho báu này, Huy đối diện với một thách thức cuối cùng - giải mã mật khẩu kỳ lạ.

Trên chiếc khóa đặc biệt này, Huy phát hiện có hai dãy ô nằm ngang có cùng độ dài, mỗi ô chứa một con số. Đặc biệt, dãy ở phía dưới có thể xoay như một vòng tròn, tức là sau mỗi lần xoay, mỗi con số sẽ di chuyển sang trái một ô, và ô đầu tiên sẽ trở thành ô cuối cùng.

Huy quyết định thử tính tổng của tích từng cặp số tương ứng giữa hai dãy ô, ghi chép lại kết quả, xoay dãy ở phía dưới và lặp lại quá trình này. Một lúc sau, Huy rút ra dự đoán rằng mật khẩu cần tìm là tổng của \(k\) số đầu tiên theo ghi chép của mình.

Tuy nhiên, vì \(k\) quá lớn nên Huy khó có thể tự tìm ra mật khẩu. Anh ta hy vọng bạn có thể giúp anh ta vượt qua thách thức này và giành được rương kho báu mơ ước.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((1 \leq n \leq 10^5, 1 \leq k \leq 10^9)\) lần lượt là số lượng ô của cả hai dãy và số lượng số cần tính toán.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\) là những số được ghi trong mỗi ô của dãy phía trên.
• Dòng tiếp theo chứa \(n\) số nguyên \(b_1, b_2, \ldots, b_n\) \((1 \leq b_i \leq 10^9)\) là những số được ghi trong mỗi ô của dãy phía dưới.

Output

• Một số nguyên duy nhất là mật khẩu mà bạn tìm được. Vì số có thể rất lớn nên bạn chỉ cần in phần dư của nó khi chia cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(28\%\) số điểm): \(n, k \leq 10^3\).
• Subtask \(2\) (\(33\%\) số điểm): \(n \leq 10^3\).
• Subtask \(3\) (\(39\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

5 3
1 2 3 4 5
6 7 8 9 10

Output

365

Note

Linh là một bạn học sinh giỏi và chấp hành nghiêm chỉnh luật giao thông. Mỗi buổi sáng, Linh sẽ đi từ nhà đến trường trên một tuyến đường cố định mà bạn thích.

Trên tuyến đường này, Linh phải đi qua \(n\) nút giao thông. Các nút giao thông được đánh số lần lượt \(1, 2, 3, \ldots, n\). Thời gian để di chuyển từ nút giao thông \(i\) \((1 \le i <n)\) đến trước nút giao thông \(i+1\) là \(t_i\) giây. Ngoài ra, thời gian để Linh từ nhà đến nút \(1\) và từ nút \(n\) đến trường là không đáng kể (xem như bằng \(0\)), nhưng Linh vẫn phải chờ đèn đỏ tại nút \(n\) trước khi đến trường nếu có.

Mỗi nút giao thông đều có đèn tín hiệu, đèn tín hiệu tại nút giao thông thứ \(j\) \((1 \le j \le n)\) có \(r_j\) giây đèn đỏ và \(g_j\) giây đèn xanh. Tại thời điểm \(0\), đèn tín hiệu ở nút \(j\) vừa chuyển sang màu \(c_j\).

Ngày hôm nay, Linh cần mua \(k\) món đồ trước khi đến trường, các món đồ cũng được đánh số \(1, 2, \ldots, k\). Trước mỗi nút giao thông có một cửa hàng tiện lợi. Do đó, Linh sẽ dừng lại và mua đồ tại một số cửa hàng dọc đường.

Cửa hàng tại nút giao thông thứ \(j\) bán một vài trong \(k\) món đồ mà Linh cần mua (có thể không bán món nào mà Linh cần) và nếu Linh dừng lại mua đồ ở đây sẽ mất \(p_j\) giây. Lưu ý rằng Linh dừng lại mua đồ trước rồi mới di chuyển đến nút giao thông tương ứng, nếu tại thời điểm mua xong mà đèn tín hiệu chuyển đỏ, Linh vẫn phải chờ đèn chuyển xanh rồi mới tiếp tục đi.

Hãy xác định thời điểm sớm nhất mà Linh có thể đến trường và mua hết \(k\) món đồ. Biết rằng mỗi món đồ được bán tại ít nhất một trong các cửa hàng dọc đường đến trường của cô ấy.

Input

• Dòng đầu tiên gồm hai số nguyên \(n\) và \(k\) \((1 \le n \le 10^5, 0 \le k \le 5)\) lần lượt là số nút giao thông trên đường đến trường của Linh và số món đồ Linh cần mua.
• Dòng tiếp theo gồm \(n-1\) số nguyên \(t_1, t_2, \ldots, t_{n-1}\) \((1 \le t_i \le 10^9)\) là thời gian di chuyển giữa các nút giao thông kề nhau.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(r_i\), \(g_i\) và kí tự \(c_i\) \((1 \le r_i, g_i\le 10^9, c_i \in \{\tt{R}, \tt{G}\})\) lần lượt là số giây đèn đỏ, số giây đèn xanh và màu của đèn tại thời điểm \(0\), \(c_i=\tt{R}\) cho biết đèn màu đỏ, \(c_i = \tt{G}\) cho biết đèn màu xanh.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) có dạng:
  • Đầu tiên là số nguyên \(p_i\) \((1 \le p_i \le 10^9)\) cho biết thời gian nếu mua đồ tại cửa hàng ở nút giao thông \(i\).
  • Tiếp theo là số nguyên \(s_i\) \((0 \le s_i \le k)\) cho biết số món đồ ở cửa hàng mà Linh cần, theo sau là \(s_i\) số nguyên là số thứ tự của các món đồ được bán theo thứ tự tăng dần.

Output

• Gồm một dòng duy nhất ghi thời điểm sớm nhất Linh đến trường và mua đủ các món đồ cần thiết.

Scoring

• Subtask \(1\) (\(26\%\) số điểm): \(k = 0\).
• Subtask \(2\) (\(28\%\) số điểm): \(k = 1\).
• Subtask \(3\) (\(46\%\) số điểm): Không có ràng buộc gì thêm.

Example

4 0
1 2 3
1 1 R
1 2 G
2 1 R
2 2 G
1 0
1 0
1 0
1 0

8

4 1
1 2 3
1 1 R
1 2 G
2 1 R
2 2 G
4 1 1
3 1 1
2 0
1 1 1

9

4 3
1 2 3
1 1 R
1 2 G
2 1 R
2 2 G
4 2 2 3
3 1 2
2 1 3
1 2 1 3

12

An là một đầu bếp tài giỏi và là một trong số ít người vào được vòng chung kết cuộc thi MathChef. Hôm nay là ngày diễn ra vòng chung kết, ban tổ chức chuẩn bị cho mỗi thí sinh một tủ nguyên liệu gồm \(n \times m\) ô tủ với \(n\) hàng ngang và \(m\) hàng dọc. Ô tủ ở vị trí \((i,j)\) là ô tủ ở hàng thứ \(i\) tính từ trên xuống dưới và cột thứ \(j\) tính từ trái sang phải, mỗi ô tủ \((i, j)\) chứa một loại nguyên liệu khác nhau với số lượng là \(a_{i,j}\).

Cuộc thi sẽ diễn ra như sau, cuộc thi gồm có \(q\) vòng, ở mỗi vòng ban giám khảo sẽ chọn ra một hình tam giác vuông cân có một cạnh song song với đường thẳng ngang và một cạnh song song với đường thẳng đứng và đặt tam giác lên trước tủ nguyên liệu sao cho tam giác khớp với một số ô tủ mà không bị lệch ra ngoài. Dưới đây là ví dụ về các tam giác vuông cân hợp lệ:

Sau đó, họ chọn ra các ô tủ nằm trong tam giác và yêu cầu thí sinh dùng các loại nguyên liệu nằm trong các ô tủ đó với số lượng tùy ý (ít nhất là \(1\) và không vượt quá số lượng ban đầu) để chế biến món ăn.

Biết rằng người làm ra món ăn ngon nhất sẽ được điểm ở vòng thi đó, An cố gắng nghĩ cách chọn và sử dụng nguyên liệu một cách hiệu quả nhất để chiến thắng cuộc thi, nhưng để làm được điều đó anh phải biết được số lượng cách chọn nguyên liệu khác nhau từ yêu cầu của giám khảo. Lưu ý, sau mỗi vòng thi, tủ nguyên liệu của mỗi thí sinh sẽ được làm đầy lại, tức là số lượng nguyên liệu của mỗi ô tủ sẽ trở về ban đầu.

Yêu cầu: Từ mỗi tam giác được chọn bởi ban giám khảo, bạn hãy in ra số lượng cách chọn nguyên liệu khác nhau mà An có thể chọn. Hai cách chọn là khác nhau khi và chỉ khi tồn tại một loại nguyên liệu có số lượng ở hai cách chọn đó là khác nhau.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n, m \leq 1000)\) lần lượt là số hàng và số cột của tủ nguyên liệu.
• Trong \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) số nguyên \(a_{i,j}\) \((1 \leq a_{i,j} \leq 10^9)\) là số lượng nguyên liệu ở ô \((i,j)\).
• Dòng tiếp theo chứa số nguyên \(q\) \((1 \leq q \leq 2 \times 10^5)\) là số vòng thi của trận chung kết.
• Trong \(q\) dòng tiếp theo, mỗi dòng chứa sáu số nguyên dương \(x_1\), \(y_1\), \(x_2\), \(y_2\), \(x_3\) và \(y_3\) \((1 \leq x_1, x_2, x_3 \leq n, 1 \leq y_1, y_2, y_3 \leq m)\) lần lượt là vị trí ba đỉnh của tam giác là các ô \((x_1, y_1)\), \((x_2, y_2)\) và \((x_3, y_3)\). Dữ liệu đảm bảo ba đỉnh tạo này thành một tam giác vuông cân hợp lệ.

Output

• In ra \(q\) dòng, mỗi dòng in ra số lượng cách chọn nguyên liệu khác nhau, lấy phần dư khi chia cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(26\%\) số điểm): \(n, m \leq 50\).
• Subtask \(2\) (\(43\%\) số điểm): \(n, m \leq 500\).
• Subtask \(3\) (\(31\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

4 5
1 2 3 4 5
5 6 7 8 9
9 8 7 6 5
4 3 2 1 9
5
2 2 2 3 3 2
2 2 3 3 2 3
1 1 4 1 4 4
1 5 1 2 4 5
1 4 3 4 3 2

Output

336
294
362880
16329600
75264

Note

Dưới đây là các hình tam giác vuông cân ở mỗi vòng thi:

Giang là một nhà khoa học tài ba, chuyên nghiên cứu về đồ thị, đặc biệt là cây.

Hôm nay Giang đang tìm hiểu về một đồ thị vô hướng gồm \(n\) đỉnh, các đỉnh được nối với nhau bằng \(n - 1\) cạnh có trọng số sao cho từ một đỉnh có thể đi đến tất cả các đỉnh còn lại.

Bây giờ Giang sẽ thực hiện một số truy vấn trên đồ thị, cụ thể anh sẽ thực hiện \(q\) truy vấn. Giả sử đồ thị có một tập các đỉnh đặc biệt, đỉnh G của đồ thị (được đặt theo tên viết tắt của anh) lúc này được định nghĩa là đỉnh có tổng khoảng cách đến tất cả các đỉnh đặc biệt là bé nhất (có thể tồn tại nhiều đỉnh G), giá trị G chính là tổng khoảng cách của đỉnh G đến tất cả các đỉnh đặc biệt.

Bây giờ với mỗi truy vấn, anh sẽ chọn ra \(m\) đỉnh trên đồ thị lần lượt là \(a_{1}, a_{2}, a_{3}, \ldots, a_{m}\). Với mỗi giá trị \(x\) sao cho \(1 \leq x \leq m\), Giang yêu cầu bạn tính giá trị G nếu tập đỉnh đặc biệt là \(a_{1}, a_{2}, \ldots, a_{x}\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 2 \times 10^{5})\).
• Trong \(n - 1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\) và \(w\) \((1 \leq u, v \leq n, 1 \leq w \leq 10^{6})\) biểu thị có cạnh nối hai đỉnh \(u\) và \(v\) với trọng số là \(w\).
• \(q\) dòng tiếp theo là các truy vấn, mỗi truy vấn gồm một dòng bắt đầu bởi số nguyên \(m\) \((1 \leq m \leq n)\) là độ dài của dãy \(a\), tiếp sau đó lần lượt là dãy \(a_{1}, a_{2}, \ldots, a_{m}\) \((1 \leq a_i \leq n, a_i \neq a_j \ \forall i \neq j)\). Gọi \(M\) là tổng giá trị \(m\) trong tất cả truy vấn, dữ liệu đảm bảo rằng \(M \leq 6 \times 10^{5}\).

Output

• Gồm \(q\) dòng, mỗi dòng gồm \(m\) số lần lượt là giá trị G cho các số \(x\) từ \(1\) đến \(m\) nếu chọn tập \(a_{1}, a_{2}, \ldots, a_{x}\) làm các đỉnh đặc biệt.

Scoring

• Subtask \(1\) (\(17\%\) số điểm): \(n, M \leq 5000\).
• Subtask \(2\) (\(19\%\) số điểm): Cây có dạng đường thẳng.
• Subtask \(3\) (\(20\%\) số điểm): \(m = 3\) trong mỗi truy vấn.
• Subtask \(4\) (\(21\%\) số điểm): \(w = 1\) trong mỗi cạnh.
• Subtask \(5\) (\(23\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

10 2
3 5 2
5 6 2
6 7 2
6 8 2
8 9 1
2 4 1
4 10 2
3 4 1
1 3 2
5 1 2 3 4 5
4 4 1 5 2

Output

0 4 4 5 7 
0 3 5 7

Note

Bài hát All I Want For Christmas Is You của Mariah Carey trên sóng phát thanh hàng năm chính là báo hiệu một mùa Giáng sinh đang cận kề. Khi ngày kỷ niệm Chúa giáng trần tới gần, cũng là lúc mà Ông già Noel bận bịu nhất.

Năm nay, để tự động hóa quá trình đóng gói quà cho các em thiếu nhi trên khắp thế giới, Ông già Noel đã kết hợp công nghệ 4.0 với sức mạnh phép thuật để cho ra đời một dây chuyền sản xuất và đóng gói quà. Băng chuyền có độ dài là \(10^9 + 1\) ô, được đánh số từ \(0\) tới \(10^9\) từ trái sang phải. Ban đầu, trên băng chuyền sẽ có \(10^9 + 1\) món quà, cũng được đánh số từ \(0\) tới \(10^9\), và mỗi quà \(i\) sẽ nằm trên ô \(i\). Lúc này, cứ mỗi giây, một chiếc cần cẩu siêu to khổng lồ sẽ gắp một số món quà trên băng chuyền chuyển qua hệ thống đóng gói. Cụ thể hơn, cứ mỗi giây, hệ thống hoạt động như sau:

• Cần cẩu gắp đúng \(k\) món quà ở các ô \(a_1, a_2, \ldots, a_k\) đi.
• Băng chuyền sẽ đẩy các món quà về bên trái cho tới khi không còn ô trống nào trừ \(k\) ô ở bên phải ngoài cùng băng chuyền.
• Hệ thống sẽ sản xuất thêm \(k\) món quà mới, được đánh số bằng \(k\) số tự nhiên nhỏ nhất sao cho chưa từng có món quà nào được đánh số bởi các số này.
• Băng chuyền sẽ đặt \(k\) món quà vừa sản xuất vào \(k\) ô trống nêu trên của băng chuyền theo thứ tự tăng dần từ trái sang phải.

Giả định bạn đảm nhiệm trọng trách vận hành hệ thống này. Cho trước danh sách các ô \(a_1, a_2, \ldots, a_k\), bạn được yêu cầu thiết kế một chương trình quản lý để trả lời được các câu hỏi sau:

• Câu hỏi loại \(1\): Món quà \(x\) sẽ được gắp đi sau tối thiểu bao nhiêu giây?
• Câu hỏi loại \(2\): Sau \(y\) giây, món quà ở ô thứ \(x\) của băng chuyền là món quà nào?

Input

• Dòng đầu tiên chứa hai số nguyên \(k\) và \(q\) (\(1 \leq k, q \leq 5 \times 10^4\)) lần lượt là số lượng món quà sẽ được gắp mỗi giây và số lượng truy vấn.
• Dòng tiếp theo chứa \(k\) số nguyên \(a_1, a_2, \ldots, a_k\) (\(0 \leq a_1 < a_2 < \ldots < a_k \leq 10^9\)) cho biết vị trí các ô sẽ được gắp quà đi mỗi giây.
• Dòng thứ \(i\) trong số \(q\) dòng tiếp theo mô tả câu hỏi thứ \(i\), cụ thể như sau:
  • 1 x: là câu hỏi loại \(1\), yêu cầu cho biết món quà \(x\) (\(0 \leq x \leq 10^9\)) sẽ được gắp đi sau tối thiểu bao nhiêu giây, in ra -1 nếu món quà không thể được gắp đi.
  • 2 x y: là câu hỏi loại \(2\), yêu cầu cho biết sau \(y\) giây, món quà ở ô thứ \(x\) của băng chuyền là món quà nào. Dữ liệu đảm bảo \(0 \leq x, y \leq 10^9\) với mọi truy vấn loại này.

Output

• Gồm \(q\) dòng, dòng thứ \(i\) gồm một số nguyên duy nhất là câu trả lời cho câu hỏi thứ \(i\), cụ thể như sau:
  • Với câu hỏi loại \(1\), in ra số giây tối thiểu để món quà \(x\) được gắp đi.
  • Với câu hỏi loại \(2\), in ra số thứ tự của món quà đang ở ô thứ \(x\) sau \(y\) giây.

Scoring

• Subtask \(1\) (\(33\%\) số điểm): \(k, q \leq 2000\).
• Subtask \(2\) (\(18\%\) số điểm): \(q \leq 30\).
• Subtask \(3\) (\(27\%\) số điểm): Không có câu hỏi loại \(2\).
• Subtask \(4\) (\(22\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 2
1 3 5
1 6
2 4 2

2
10