Hello, codeforces!

Recently I came up with a task, but I couldn't solve it.

The task is:

You are given a two arrays a and b of size n (1 ≤ n ≤ 10⁵). You should answer q (1 ≤ q ≤ 10⁵) queries:

• for given integer k (1 ≤ k ≤ n) you need to find maximal value a_i + b_k - i.