Negate Range Updates on Array

A data analyst has an array data of length n representing data for n days. He performs k updates in order; each update is [l, r], meaning every element from index l to r (inclusive, 1-indexed) is negated (x becomes −x).

Find the array after all updates are done.

输入格式

The first line contains an integer n, and the second line contains n integers data[1..n]. The third line contains an integer k, followed by k lines with two integers l r each.

1≤n≤10^6, 1≤k≤10^6, |data[i]|≤10^9, 1≤l≤r≤n.

输出格式

Output one line with the n integers of the final array, separated by spaces.

样例 1

输入：

4
1 -4 -5 2
2
2 4
1 2

输出：

-1 -4 5 -2

样例 2

输入：

5
1 2 3 4 5
2
1 3
2 4

输出：

-1 2 3 -4 5

样例 3

输入：

3
0 -7 1000000000
3
1 3
1 3
2 2

输出：

0 7 1000000000

样例说明

Example 1: after the first update [2,4] the array is [1,4,5,−2], and after the second update [1,2] it is [−1,−4,5,−2]. Example 2: after [1,3] it is [−1,−2,−3,4,5], and after [2,4] it is [−1,2,3,−4,5]. Example 3: applying [1,3] twice changes nothing, and then the 2nd element is negated; negating 0 still gives 0.