The Return of the Wayward Parrot

In this task, Wolf wants to teach Kesha how to count by playing a game. Wolf writes down a sequence of numbers and gives Kesha pairs of numbers, (l) and (r). For each pair, Kesha must find a subsequence within the range such that the sum of its elements,

[ a_i + a_i+1 + ...+ a_j-1 + a_j, ]

where (i) and (j) are between (l) and (r), is maximized. Each morning, Wolf may change some numbers in the array, and each evening, he presents Kesha with one or more similar tasks.

Your task is to assist Kesha by writing a program that finds the maximum sum under these conditions.

Input

The first line contains the numbers (N) and (D) ((1 $\le$ N, D $\le$ 10^6))—the length of the sequence and the number of days Wolf teaches Kesha. The second line contains (N) numbers, representing the initial state of the sequence. Each number does not exceed (10^9) in absolute value. Following this, (M) ((1 $\le$ M $\le$ 10^5)) indicates the number of days Wolf modifies the sequence. The next (M) lines each contain three numbers: (d), (x), and (y), where (d) is the day number, (x) is the position of the element being changed, and (y) is the new value of this element. The days are provided in chronological order, and each day number does not exceed (D). On any given day, Wolf may change multiple elements. After this, the number (K) ((1 $\le$ K $\le$ 10^5)) indicates the number of days Kesha seeks your help. Each query consists of two numbers, (l) and (r), which define the boundaries of the segment where you need to calculate the maximum sum. The day Kesha contacts you for each query is determined by:

[ d = (z + i) % D + 1, ]

where (z) is the answer to the previous query (for the first query, assume (z = 0)), and (i) is the current query number. All query numbers and positions in the sequence start from one.

Output

Output (K) lines, each containing one number—the answer to the corresponding query.

Examples