Những viên đá của Kuriyama

Kuriyama có $N$ viên đá, đánh số từ $1$ đến $N$. Viên đá thứ $i$ có giá trị $v_i$.

Gọi $u_i$ là giá trị của viên đá rẻ thứ $i$, tức là dãy $u$ thu được bằng cách sắp xếp dãy $v$ theo thứ tự không giảm.

Bạn cần trả lời $M$ truy vấn, mỗi truy vấn thuộc một trong hai loại:

• Loại $1$: cho hai số $l,r$, hãy tính $v_l+v_{l+1}+\dots +v_r$.
• Loại $2$: cho hai số $l,r$, hãy tính $u_l+u_{l+1}+\dots +u_r$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $N$.
• Dòng thứ hai chứa $N$ số nguyên $v_1,v_2,\dots ,v_N$.
• Dòng thứ ba chứa số nguyên $M$.
• $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $type,l,r$ mô tả một truy vấn: nếu $type=1$ thì đây là truy vấn loại $1$, ngược lại ($type=2$) là truy vấn loại $2$.

Dữ liệu ra

In ra $M$ dòng, dòng thứ $i$ là đáp án của truy vấn thứ $i$.

Ràng buộc

• $1\le N,M\le {10}^5$
• $1\le v_i\le {10}^9$
• $1\le l\le r\le N$

Ví dụ