Game thiện xạ VNOI Shooter tổ chức sự kiện One shot mỗi năm một lần. Thể lệ sự kiện rất đơn giản như sau:

• Mỗi trận gồm ~n~ người chơi đứng trên một vòng tròn đủ lớn theo thứ tự tăng dần theo chiều kim đồng hồ. Tức người chơi ~i~ đứng tiếp sau người chơi ~i - 1~ và người tiếp theo của người chơi ~n~ chính là người chơi ~1~.

• Trước khi bắt đầu trận, họ sẽ đưa số coin mà họ cược. Người chơi ~i~ sẽ cược ~a_i~ coin.

• Sau khi tất cả cược xong, hệ thống sẽ phát cho mỗi người chơi một cây súng ngẫu nhiên. Người chơi thứ ~i~ sở hữu cây súng có tầm bắn từ ~l_i~ đến ~r_i~ theo chiều kim đồng hồ.

• Khi bắt đầu vòng chơi, hệ thống sẽ đếm ngược thời gian để các xạ thủ có thể nhắm vào một mục tiêu của mình. Khi đồng hồ đếm ngược kết thúc, các xạ thủ sẽ đồng thời bắn.

• Sau khi lượt bắn kết thúc, những ai còn sống sót là người chơi thắng, và họ sẽ được hệ thống thưởng đúng số tiền họ cược. Ngược lại, những người chơi thua sẽ bị mất tiền cược.

• Giả sử xác suất một người nhắm vào một trong các mục tiêu của họ là như nhau. Trong một trận cụ thể, sau khi biết hết số tiền người chơi cược và loại súng của họ, hãy tính xem giá trị kỳ vọng là số coin mà hệ thống nhận được sau trận này.

Input

Dữ liệu vào từ file văn bản oneshot.inp:

Dòng đầu tiên gồm một số nguyên dương ~n~ (~2 \le n \le 2 \cdot 10^5~) - số lượng người chơi.

Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^5~)- với ~a_i~ là số coin mà người chơi thứ ~i~ cược.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo có hai số nguyên dương ~l_i~ và ~r_i~ (~1 \le l_i, r_i \le n~) - tầm bắn của cây súng của người chơi thứ ~i~.

Output

In ra file văn bản oneshot.out. Đặt ~M = 10^9 + 7~. Giá trị kỳ vọng của số coin mà hệ thống nhận được sau trận có thể được biểu diễn dưới dạng một phân số tối giản ~\frac{P}{Q}~, với ~P~ và ~Q~ là hai số nguyên và ~Q \not\equiv 0 \pmod{M}~. Hãy in ra ~P \cdot Q^{-1} \pmod{M}~, hay nói cách khác, in ra một số nguyên ~X~ thỏa mãn ~0 \le X < M~ và ~X \cdot Q \equiv P \pmod{M}~.

Scoring

Sample Input 1

4
7 3 3 7
4 4
4 1
3 2
3 2

Sample Output 1

812500015

Sample Input 2

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

Sample Output 2

851428591

Note

Ở ví dụ thứ nhất:

• Người thứ nhất nằm trong tầm bắn của người thứ hai, thứ ba và thứ tư. Tỉ lệ người thứ nhất sống sót là ~\frac{9}{32}~.
• Người thứ hai nằm trong tầm bắn của người thứ ba và thứ tư. Tỉ lệ người thứ hai sống sót là ~\frac{9}{16}~.
• Người thứ ba nằm trong tầm bắn của người thứ ba và thứ tư. Tỉ lệ người thứ ba sống sót là ~\frac{9}{16}~.
• Người thứ tư nằm trong tầm bắn của người thứ nhất, thứ ba và thứ tư. Tỉ lệ người thứ tư sống sót là ~0~.

Giá trị kỳ vọng số coin mà hệ thống nhận được là: ~-7 \cdot \frac{9}{32}+ 7 \cdot(1-\frac{9}{32})-3\cdot \frac{9}{16}+ 3\cdot (1-\frac{9}{16})-3\cdot \frac{9}{16}+3 \cdot (1- \frac{9}{16})+ 7 = \frac{149}{16}~.

Vì ~16^{-1} \equiv 562500004 \pmod{M}~, in ra kết quả là ~(149 \cdot 562500004) \equiv 812500015 \pmod{M}~.

Các bạn tình nguyện viên Bedao quyết định di cư sang thành phố VNOI để sinh sống. Thành phố gồm ~n~ ngôi nhà và ~n - 1~ con đường hai chiều nối trực tiếp hai ngôi nhà trong thành phố. Hệ thống đường xá của thành phố VNOI rất tối ưu nên từ một ngôi nhà có thể đến bất kỳ ngôi nhà nào thông qua các con đường.

Gen mới gồm một số bạn tình nguyện viên, mỗi bạn sẽ được bố trí một ngôi nhà khác nhau. Hàng ngày, các sếp lớn Bedao đều đi qua nhà mỗi bạn để giám sát nên cần một cách bố trí tối ưu để tiết kiệm thời gian. Cụ thể, chi phí cho một cách bố trí ~k~ ngôi nhà là tổng độ dài đường đi ngắn nhất từ ngôi nhà ~1~ đi qua tất cả ~k~ ngôi nhà. Do số lượng các bạn Gen mới chưa được quyết định, các sếp muốn tìm ra các cách bố trí có chi phí nhỏ nhất cho tất cả ~n~ trường hợp: Gen mới gồm ~1~ bạn tình nguyện viên, ~2~ bạn tình nguyện viên, ~\cdots~, ~n~ bạn tình nguyện viên.

Input

Dữ liệu vào từ file văn bản migration.inp:

Dòng đầu tiên gồm hai số nguyên ~n~ (~1 \le n \le 5000~) — số ngồi nhà trong thành phố.

Trong ~n - 1~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên ~u_i~, ~v_i~ và ~w_i~ (~1 \le u_i, v_i \le n~, ~1 \le w_i \le 10^9~, ~u_i \ne v_i~) — con đường trực tiếp nối hai ngôi nhà ~u_i~ và ~v_i~ với thời gian di chuyển ~w_i~.

Dữ liệu đảm bảo rằng bố cục các ngôi nhà tạo thành cây, và từ một ngôi nhà có thể đến bất kỳ ngôi nhà nào chỉ thông qua các con đường.

Output

In ra file văn bản migration.out trên ~n~ dòng, dòng thứ ~i~ là chi phí nhỏ nhất của cách bố trí tối ưu ~i~ bạn tình nguyện viên vào các ngôi nhà.

Scoring

Sample Input 1

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

Sample Output 1

0
1
2
3
5
7
9

Notes

Trong ví dụ trên, với ~k = 5~, các sếp sẽ bố trí ~5~ bạn tình nguyện viên vào các ngôi nhà ~1, 2, 3, 5, 7~. Như vậy mỗi ngày các sếp chỉ cần di chuyển như sau: ~1 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 5 \rightarrow 7~ và đây là cách bố trí tối ưu.

Có ~N~ hình chữ nhật trên mặt phẳng tọa độ. Các hình chữ nhật có thể giao hoặc không giao nhau và có thể trùng nhau.

Cho ~2~ số nguyên ~L~ và ~R~. Đếm số lượng điểm bị phủ bởi ít nhất ~L~ hình chữ nhật, và nhiều nhất ~R~ hình chữ nhật.

Input

Dữ liệu vào từ file văn bản rect.inp:

Dòng đầu tiên gồm ~3~ số nguyên dương ~N~, ~L~, ~R~ (~1 \le L \le R \le N \le 2 \cdot 10^5~).

~N~ dòng tiếp theo gồm ~4~ số nguyên ~x_1~, ~y_1~, ~x_2~, ~y_2~ tương ứng là tọa độ góc trái dưới và góc phải trên của hình chữ nhật thứ ~i~. (~0 \le x_1 \le x_2 \le 10^5, 0 \le y_1 \le y_2 \le 10^5~).

Output

In ra file văn bản rect.out một số nguyên duy nhất là kết quả bài toán.

Scoring

Sample Input 1

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

Sample Output 1

25

Sample Input 2

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

Sample Output 2

43