Invert Range

You are given a sequence of n integers and m spells. Each spell is represented by a pair of indices [start, end] (0-indexed), indicating the positions in the sequence where the sign of the integer should be inverted (i.e. multiplied by -1). The spells are applied sequentially.

Input Format: The first line contains a single integer n. The second line contains n space-separated integers representing the sequence. The third line contains a single integer m representing the number of spells. Each of the next m lines contains two integers start and end (with 0 ≤ start ≤ end < n), denoting the range of indices for which to invert the values.

Output Format: Output the final state of the sequence after applying all spells. The sequence should be printed on one line with each integer separated by a space.

Example:

Input:
5
1 -2 3 -4 5
2
1 3
2 4
Output:
1 2 3 -4 -5

</p>

inputFormat

The input is given via standard input (stdin) with the following structure:

1. An integer n indicating the number of elements in the sequence.
2. A line containing n space-separated integers.
3. An integer m representing the number of spells.
4. m lines follow, each containing two integers start and end defining the range (inclusive) in the sequence.

outputFormat

Output the resulting sequence after all spells are applied. The numbers must be printed on one line separated by a space, via standard output (stdout).

## sample

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

1 2 3 -4 -5