Tèo học Đại học Giao thông vận tải, trong dịp nghỉ lễ Tèo về quê đi bắt cua.

Có n lỗ cua thẳng hàng nhau mỗi lỗ cua có số lượng cua lần lượt là $a_1,a_2,...a_n$. Đáng lẽ ra thì Tèo sẽ bắt đượt hết tất cả các con cua, nhưng có 3 con rắn mỗi con có khả năng quản lý lần lượt là $x,y,z$ số lỗ cua liên tiếp nhau khiến Tèo không bắt được cua trong những lỗ đó.

Ba con rắn này rất tinh quái phân công quản lý làm sao mà được số cua nhiều nhất nên bọn nó tự phân công vị trí trông coi không cho Tèo bắt cua. Biết rằng thứ tự phân công phải lần lượt từ trái sang phải tức là

• Con rắn 1 quản lý $x$ lỗ nằm ở phía trái

• Con rắn 2 quản lỹ $y$ lỗ nằm ở giữa

• Con rắn 3 quản lý $z$ lỗ nằm ở phía phải

Bạn hãy lập trình tính số cua Tèo bắt được

Input

Dòng đầu gồm $n$ là số lượng lỗ cua $(1\le n\le {10}^5)$

Dòng tiếp theo gồm n số tự nhiên có giá trị không vượt quá $1000$ là số lượng cua lần lượt của từng lỗ

Tiếp theo là số lượng truy vấn $q(1\le q\le 100)$

Tiếp theo là $q$ dòng mỗi dòng gồm 3 giá trị $x,y,z(1\le x,y,z\le n)$ tương ứng là số lỗ cua liên tiếp nhau mà từng con rắn quản lý

Ouput

Gồm $q$ dòng mỗi dòng là một đáp án cho một truy vấn

Ví dụ

Input

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

Output

16

Giải thích: Bọn rắn phân công như sau

Con rắn 1 quản lý được 1 lỗ $a_2$

Con rắn 2 quản lý được 1 lỗ $a_4$

Con rắn 3 quản lý được 2 lỗ liên tiếp $a_5,a_6$

Nên Tèo chỉ bắt được số cua là $4+2+3+2+5=10$