A binary search tree (BST) is built from an empty tree by inserting the given keys one at a time, in the order they appear (go left for smaller keys, right for larger, dropping the key at the first empty spot). All inserted keys are distinct.\n\nThen answer several independent range queries. For each query lo hi (with lo <= hi), report the sum of all keys x stored in the tree that satisfy lo <= x <= hi. If no key falls in the range, the sum is 0.\n\n## Input format\n\nLine 1: two integers n and q.\nLine 2: n distinct space-separated integers giving the insertion order.\nNext q lines: each contains two integers lo and hi (lo <= hi).\n\n## Output format\n\nq lines. Line i is the sum of stored keys in the closed range of the i-th query.\n\n## Constraints\n\n- 1 <= n <= 100000\n- 1 <= q <= 100000\n- -1000000000 <= each key <= 1000000000, and all keys are distinct.\n- -1000000000 <= lo <= hi <= 1000000000.\n- Sums fit in a signed 64-bit integer.