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