Lẩu băng chuyền là một hình thức ăn lẩu trong đó thực khách ngồi quanh một băng chuyền chạy vòng tròn, trên đó có các đĩa nhỏ chứa các loại nguyên liệu tươi sống như thịt, hải sản, rau củ và các loại nấm. Thực khách có thể tùy ý lựa chọn nguyên liệu mà mình muốn và cho vào nồi lẩu đang sôi trước mặt.

Hôm nay, để giải tỏa stress sau buổi ngày ôn luyện căng thẳng, lithium đã đi ăn cho đã đời rồi ôn luyện tiếp. Trên băng chuyền hiện tại có ~n~ đĩa đồ ăn được đặt trên BĂNG CHUYỀN HÌNH TRÒN có độ ngon và giá tiền khác nhau. Anh ấy nghĩ rằng, cái bụng của ảnh chỉ chứa được ~k~ đĩa đồ ăn. Vì là một người có tiền nên anh ấy muốn ăn một cách ngon miệng (anh ấy sẽ tối đa hóa độ ngon rồi mới cực tiểu hóa số tiền). Vì là một người bị OCD nên anh ấy phải chọn ~k~ đĩa đồ ăn liên tiếp. Nhưng vì học quá mệt mỏi nên lithium nhờ bạn tìm cách sao cho giúp anh ấy ăn ngon miệng nhất có thể để anh ấy có sức học tiếp 😋😋😋.

Input

Dòng đứa cho số nguyên dương ~n, k~ tượng trưng cho số đĩa trên băng chuyền và số lượng đĩa anh ấy chọn.

Dòng tiếp theo chứa dãy số ~d_1, d_2, \dots, d_i, \dots, d_n~ tượng trưng cho độ ngon của món ăn ~i~.

Dòng tiếp theo chứa dãy số ~c_1, c_2, \dots, c_i, \dots, c_n~ tượng trưng cho giá tiềncủa món ăn ~i~.

Output

Ghi ra độ ngon lớn nhất và giá tiền ít nhất khi chọn ~k~ đĩa liên tiếp trên băng chuyền HÌNH TRÒN (ưu tiên độ ngon).

Constraints

~k \leq n \leq 10^6~

~-10^6 \leq d_i \leq 10^9~

~1 \leq c_i \leq 10^9~

Sample Input 1

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

Sample Output 1

9 7

Sample Input 2

5 2
5 2 5 4 5
100 2 3 4 5

Sample Output 2

10 105

Note

Ở Sample Test 1: Chọn đĩa ~3, 4~ là tối ưu.

Ở Sample Test 2: Chọn đĩa ~5, 1~ là tối ưu (vẫn thỏa mãn chọn ~k~ đĩa liên tiếp).

hieuhfgr là một người thích vẽ. Hiện tại hieuhfgr đang sở hữu ~n~ cây bút màu được đựng trong một hộp hàng ngang, cây bút thứ ~i~ có màu là ~a_i~. Bây giờ, hieuhfgr cần vẽ ~q~ bức tranh, bức tranh thứ ~i~ hieuhfgr sẽ lấy những cây bút màu từ vị trí ~l_i \to r_i~. Nhưng mà lấy hết mà vẽ thì chán quá!!!. hieuhfgr muốn hỏi bạn xem có bao cách chọn màu sắc khác nhau để vẽ được một bức tranh.

Định nghĩa: một bức tranh cần tối thiểu ~1~ màu sắc.

Input

Dòng 1: chứa số nguyên ~n, q~.

Dòng 2: chứa dãy số ~a~

~q~ dòng cuối mỗi dòng chứa ~l_i \to r_i~ yêu cầu nếu chọn các bút màu từ vị trí ~l_i \to r_i~ thì có bao nhiêu cách chọn màu sắc.

Output

Ghi ra ~q~ dòng là số cách chọn khi chia lấy dư cho ~10^9+7~

Contraints

~n, q \leq 10^5~

~a_i \leq 10^6~

~1 \leq l_i \leq r_i \leq n~

Sample Input 1

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

Sample Output 1

3
7
7

Sample Input 2

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

Sample Output 2

1
3
3

Note

• Sample Test 1:
• Truy vấn 1: chọn ~\{1\}, \{2\}, \{1, 2\}~

• Truy vấn 2: chọn ~\{1\}, \{2\}, \{3\}, \{1, 2\}, \{2, 3\}, \{1, 3\}, \{1, 2, 3\}~

• Sample Test 2:

• Truy vấn 1: chọn ~\{1\}~
• Truy vấn 2: chọn ~\{1\}, \{2\}, \{1, 2\}~
• Truy vấn 3: chọn ~\{1\}, \{2\}, \{1, 2\}~

"1 đời liêm khiết, ngàn đời liêm khiết..."

Sau khi tổ chức Chi Lăng Esport, lithium đã rất vui vì Chi Lăng Esport tổ chức thành công rực rỡ mà không gặp một vướng mắc nào. Nhưng còn một vấn đề nữa??? lithium đang tính tạo ra một bản đồ để phục vụ mùa giải Esport thứ 2 với bộ môn CSSGO.

"CSSGO là thể thao trí tuệ trong đó chia làm ~2~ team ~1~ và ~2~ lần lượt có chức năng là đặt bom và là gỡ bom. Sẽ có một địa điểm được chọn là điểm đặt bom. Nhiệm vụ của team gỡ bom cần phải không cho team đặt bom đặt được bom (a.k.a team gỡ bom cần phải đến trước team đặt bom để def site). Đặc biệt, trò chơi có cách di chuyển độc đáo như sau: ~2~ team sẽ đi lần lượt nhau với team ~2~ được đi trước rồi đến team ~1~ rồi đến team ~2~,...."

Bản đồ của anh được xem như đồ thị cây gồm ~n~ đỉnh ~n-1~ cạnh, trong đó bất kì ~2~ đỉnh nào cũng có đường đi (và là duy nhất). Bây giờ, lithium có ~q~ giả định, mỗi giả định lithium đưa ra vị trí khởi đầu (là chỉ số đỉnh) của team ~1~ và team ~2~. Anh ấy muốn tính toán xem có bao nhiêu vị trí đặt bom (khác hai vị trí khởi đầu) sao cho team ~2~ đến trước team ~1~ (nếu team ~1~ đến trước team ~2~ thì còn gì là CSSGO nữa 🐧).

Input

Dòng đầu chứa ~n, q~ lần lượt là số đỉnh của bản đồ và số lượng giả định

~n-1~ dòng tiếp theo, mỗi dòng tương ứng là ~(u, v)~ tương ứng là hai vị trí ~u, v~ có thể đến được.

~q~ dòng cuối cùng mỗi dòng gồm hai số nguyên ~t_1, t_2~ lần lượt là vị trí của team ~1~ và team ~2~.

Output

In ra ~q~ dòng là số lượng đỉnh thỏa mãn có thể chọn là điểm đặt bom.

Constraints

~n,q \leq 10^5~

~1 \leq t_1, t_2 \leq n \;, t_1 \neq t_2~

Sample Input

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

Sample Output

4
6
6
2

Note

Ở Sample Test, bảng tạo ra sẽ như thế này (click vào đây nếu bạn không thấy ảnh)

Giả định 1: Số đỉnh mà team ~2~ đến trước là: ~1, 2, 5, 3~

Giả định 2: Số đỉnh mà team ~2~ đến trước là: ~1, 2, 3, 5, 6, 7~

Giả định 4: Số đỉnh mà team ~2~ đến trước là: ~4, 7~