Xsquare loves to play with arrays a lot. Today, he has two arrays named as A and B. Each array consists of N positive integers.

Xsquare has decided to fulfill following types of queries over his array A and array B.

• 1 L R : Print the value of A_L + B_L+1 + A_L+2 + B_L+3 + ... upto R^th term.
• 2 L R : Print the value of B_L + A_L+1 + B_L+2 + A_L+3 + ... upto R^th term.

Input

First line of input contains two space separated integers N and Q denoting the size of arrays ( A , B ) and number of queries respectively. Next N lines of input contains N space separated integers denoting array A. Next line of input contains N space separated integers denoting array B. Next Q lines of input contains Q queries (one per line). Each query has one of the above mentioned types.

Output

Output consists of Q lines, each containing answer to the corresponding query.

Constraints

• 1 ≤ N,Q ≤ 10⁵
• 1 ≤ A_i,B_i ≤ 10⁹
• 1 ≤ L,R ≤ N