Ma trận ~A~ kích thước ~n \times n~ được gọi là trội chéo nếu thoả mãn các điều kiện sau:

1. ~\forall \ i, j \in [1,n],\ A_{ij} \ge 0~.

2. ~\forall \ i \in [1,n],\ A_{ii} \ge \sum_{j=1,\ j \ne i}^n\ A_{ij}~.

3. ~\exists \ i \in [1,n],\ A_{ii} \gt \sum_{j=1,\ j \ne i}^n\ A_{ij}~.

Phần tử ~\ A_{ii} \gt \sum_{j=1,\ j \ne i}^n\ A_{ij}~ được gọi là phần tử trội.

Yêu cầu: Cho ~n~ và ma trận ~A~, các phần tử của ma trận ~A~ là số nguyên ~(0 \le A_{ij} \leq 1000,\ 2 \le n \le 1000)~. Viết chương trình xác định xem ~A~ có phải là ma trận trội chéo hay không, nếu có thì đưa ra số lượng phần tử trội.

Input

• Dòng đầu tiên chứa số nguyên ~n~.

• Trên ~n~ dòng tiếp theo, dòng thứ ~i~ có ~n~ số nguyên xác định dòng thứ ~i~ của ma trận.

Các số trên một dòng cách nhau bởi ít nhất một dấu khoảng trắng.

Output

• Dòng đầu tiên chứa thông báo YES hoặc NO.

• Nếu kết quả là YES, dòng thứ ~2~ chứa một số nguyên cho biết số phần tử trội.

Sample Input 1

3
10 5 5
0 1 0
2 2 5

Sample Output 1

YES
2

Khi xuất hiện dịch bệnh ~X~, các nhà khoa học đã nghiên cứu sự thay đổi gene của các chứng virus. Chuỗi gene của virus là dãy ~N~ phức hợp proteins được mã hóa thành các số nguyên ~a_1, a_2, \ldots, a_N~ (~1 \le i \le N~).

Ban đầu, chuỗi gene được chứa toàn bộ các proteins ~0~. Chúng có rất nhiều lần biến đổi khác nhau. Mỗi lần biến đổi, chúng thay đổi các proteins trong đoạn ~[L, R]~ theo phép toán ~T_K~. Nghĩa là các proteins trong đoạn ~[L, R]~ tăng lên một lượng giá trị là số fibonacci thứ ~K~ chia đồng dư cho ~10^3 + 7~ (phép modulo). Với dãy số fibonacci được định nghĩa như sau: $$F_K = F_{K - 1} + F_{K - 2} \text{ với } F_1 = 1, F_2 = 1.$$

Để làm cơ sở nghiên cứu, các nhà khoa học đã ghi lại các câu truy vấn cho biết quá trình biến đổi gene. Bên cạnh đó, họ có các câu truy vấn tính tổng các proteins trong đoạn ~[L, R]~ tại một số thời điểm.

Yêu cầu: Viết chương trình thực hiện lần lượt ~Q~ truy vấn, mỗi truy vấn có thể là một trong hai dạng sau:

• ~1~ ~L~ ~R~ ~K~: Biến đổi các proteins trong đoạn ~[L, R]~ theo phép toán ~T_K~.

• ~2~ ~L~ ~R~: Tính tổng các proteins trong đoạn ~[L, R]~.

(~1 \le L \le R \le N~; ~1 \le K \le 10^{18}~).

Input

• Dòng đầu tiên chứa hai số nguyên ~N~, ~Q~ (~1 \le N, Q \le 2 \cdot 10^5~).

• Trên ~Q~ dòng tiếp theo, mỗi dòng chứa một truy vấn theo mô tả như trên.

Các số trên một dòng cách nhau bởi ít nhất một dấu khoảng trắng.

Ràng buộc: Tổng các giá trị ~a_i~ trong quá trình truy vấn sẽ không vượt quá ~10^9~.

Output

Ghi ra kết quả của các truy vấn dạng ~2~, mỗi kết quả ghi trên một dòng.

Sample Input 1

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

Sample Output 1

6
25

Sample Input 2

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

Sample Output 2

81

Notes

Giải thích:

1. • Ban đầu, các phức hợp proteins là ~\{0, 0, 0, 0, 0\}~.

   • Truy vấn đầu tiên, biến đổi đoạn ~[2, 4]~ theo ~T_3~ nghĩa là tăng lên ~2~ đơn vị nên ta có chuỗi gen ~\{0, 2, 2, 2, 0\}~.

   • Truy vấn thứ hai, tổng đoạn ~[1, 5]~ ta được giá trị là ~6~.

   • Truy vấn thứ ba và thứ tư, lần lượt là ~\{5, 7, 7, 2, 0\}~ và ~\{5, 7, 7, 10, 8\}~.

   • Truy vấn cuối cùng, tổng đoạn ~[3, 5]~ ta được ~(7 + 10 + 8) = 25~.

2. Chuỗi gene có các phức hợp proteins thay đổi lần lượt như sau: ~\{0, 0, 0\}~, ~\{5, 0, 0\}~, ~\{5, 13, 0\}~, ~\{26, 34, 21\}~. Kết quả cuối cùng sẽ là ~(26 + 34 + 21) = 81~.

Mạng lưới giao thông thành phố gồm ~N~ nút được đánh số từ ~1~ đến ~N~ và ~M~ đường một chiều nối các cặp nút. Với ý định muốn giảm được độ dài của đường đi ngắn nhất từ nút trọng yếu ~S~ đến nút ~T~ ~(S \neq T)~, một danh sách gồm ~K~ đường hai chiều được đề xuất để xem xét xây dựng.

Yêu cầu: Viết một chương trình để chọn ra một đường trong danh sách đề xuất trên để xây dựng sao cho độ dài đường đi ngắn nhất từ ~S~ đến ~T~ là nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa năm số nguyên dương ~N~ ~(N \le 10^4)~, ~M~ ~(M \le 10^5)~, ~K~ ~(K \lt 300)~, ~S~ ~(S \le N)~, ~T~ ~(T \le N)~.

• Trên ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~A_i~, ~B_i~, ~L_i~. Trong đó ~L_i~ là độ dài của đường một chiều thứ ~i~ từ nút ~A_i~ đến nút ~B_i~ ~(L_i \le 1000)~.

• Trên ~K~ dòng tiếp theo, dòng thứ ~j~ chứa ba số nguyên dương ~U_j~, ~V_j~, ~Q_j~. Trong đó ~Q_j~ là độ dài của đường hai chiều được đề xuất thứ ~j~ nối giữa hai nút ~U_j~ và ~V_j~ ~(Q_j \le 1000)~.

Các số trên một dòng cách nhau bởi ít nhất một dấu khoảng trắng.

Output

In độ dài nhỏ nhất có thể của đường đi ngắn nhất từ ~S~ đến ~T~ sau khi xây dựng xong một con đường hai chiều từ danh sách đề xuất. Trường hợp không có đường đi từ ~S~ đến ~T~ thì in ~-1~.

Sample Input 1

4 5 3 1 4
1 2 13
2 3 10
3 1 15
3 4 16
4 1 18
1 3 21
2 3 5
2 4 20

Sample Output 1

33