Hôm này PhuocThien đang đi chơi khi về nhà vô tình lạc vào \(1\) ma trận gồm \(N\) hàng và \(M\) cột ban đầu bạn ở điểm.
Mỗi bước, bạn chỉ được phép:

• Đi sang phải: từ (i, j) đến (i, j + 1).
• Đi xuống dưới: từ (i, j) đến (i + 1, j).
  Hãy tính số cách khác nhau để đi từ (1, 1) đến (M, N).

Input

• \(1\) dòng gồm số nguyên dương \(N, M\). \((1 \le N, M \le 1000)\).

Output

• Kết quả bài toán chia lấy dư cho \(10^9 + 7\).

Example

2 3

3

Scoring

• Subtask \(1\) \((50\%\) điểm\()\): \(1 \le N, M \le 30\).
• Subtask \(2\) \((50\%\) điểm\()\): Không còn ràng buộc gì thêm.

Hãy Tính Tổng từ \(i\) ⭢ \(j\).

Input

• \(1\) Dòng gồm \(2\) số nguyên dường \(i, j\). \((1 \le i \le j \le 10^{20})\).

Output

• Kết quả bài toán. (không chia lấy dự in ra toàn số nguyên kết quả).

Example

1 10

55

1 100

5050

123 1234

754492

Một con sâu đang đói bụng vô tình đã đi vào \(1\) ma trận thức ăn mà PhuocThien đã tạo ra mỗi thức ăn sẽ giúp con sâu no thêm \(a[i, j]\) đơn vị nhưng có \(2\) điều kiện cần được tuân thủ \(:\)

• Chỉ được đi theo hiệu lệnh của PhuocThien.
• Nếu đi ra ngoài thì con sau được tính là bị loại bỏ.

Hiệu lệnh của PhuocThien được hiểu như sau:

• Nếu PhuocThien nói L nghĩa là đi sang trái.
• Nếu PhuocThien nói R nghĩa là đi sang phải.
• Nếu PhuocThien nói U nghĩa là đi sang lên.
• Nếu PhuocThien nói D nghĩa là đi sang xuống.

Chú thích thêm: Con sâu không ngẫu nhiên đi vào mà phải được PhuocThien đưa đến chỗ đó.

Input

• Dòng \(1\): Số nguyên dương \(N\). \((1 \le N \le 1000)\)
• \(N\) dòng tiếp theo: với mỗi dòng nhập \(N\) sô nguyên dương \(a[i, j]\). \((1 \le a[i, j] \le 10^4)\)
• Dòng thứ \(N+1\) nhập \(Q\) truy vấn. \((1 \le Q \le 1000)\)
• Với mỗi truy vấn nhập xâu \(S\) (hiệu lệnh) và \(x\), \(y\) là tọa thả sâu\((1 \le S \le 100, 1 \le x, y \le N)\)

Output

• Nếu sâu không tuân thủ \(2\) điều kiện thì in ra -1, ngược lại thì in ra tổng giả trị mà sâu đã ăn được.

Example

2
1 2
3 4
2
RDLU
1 1
U
1 1

11
-1

3
1 2 3
4 5 6
7 8 9
3
RRD
1 1
DD
2 2
LL
1 1

12
-1
-1

Sau một sự cố an ninh mạng toàn cầu, mạng lưới máy chủ lõi gồm \(N\) máy chủ được kết nối với nhau dưới dạng một cấu trúc cây gồm \(N-1\) cáp nối quang. Mỗi cáp nối giữa máy chủ \(u\) và \(v\) có một băng thông truyền tải là \(w\). Để tái cấu trúc hệ thống một cách an toàn, bạn cần chọn ra đúng \(k\) cáp nối sao cho không có máy chủ nào kết nối trực tiếp với quá \(2\) cáp nối được chọn (tức là các cáp nối được chọn phải tạo thành một tập hợp các đường đi rời nhau về mặt đỉnh trên cây). Hãy xác định tổng băng thông lớn nhất có thể đạt được với mọi cấu hình chọn từ \(1\) đến \(N-1\) cáp nối.

Input

• Dòng đầu tiên chứa một số nguyên \(N\) (\(1 \le N \le 300\)) — số lượng máy chủ.
• \(N-1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\) và \(w\) (\(1 \le u, v \le N, |w| \le 10^9\)) mô tả một cáp nối giữa hai máy chủ \(u\) và \(v\) với băng thông \(w\).

Output

• In ra \(N-1\) số nguyên trên một dòng, số thứ \(k\) thể hiện tổng băng thông lớn nhất có thể đạt được khi chọn đúng \(k\) cáp nối thỏa mãn điều kiện. Nếu không thể chọn được đúng \(k\) cáp nối, in ra -1.

Example

5
1 2 5
2 3 10
3 4 -2
3 5 7

10 17 22 -1