Cho một số tự nhiên \(N\). Hãy liệt kê tất cả cặp số \((i,j)\) sao cho \(1 \leq i,j \leq N\)

Input

• Một số \(N (1 \leq N \leq 1000)\) duy nhất

Output

• Liệt kê các cặp số theo thứ tự tăng dần của số thứ nhất. Nếu số thứ nhất bằng nhau, hãy xếp theo số thứ hai.

Example

3

1 1
1 2
1 3 
2 1
2 2 
2 3 
3 1
3 2 
3 3 

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