Flipping a Pack of Cards

Time limit1sMemory limit128 MB

Summary

Simulate a deck of n cards under m prefix-reversal-and-flip operations, then report the final position and face direction of s queried cards.

Level: Medium6 of 10
Topics: Simulation, Implementation, Math, Array
Solved: No attempts yet

Problem

A pack of $n$ cards lies on the table, stacked one on top of another. Each card has a positive integer written on exactly one side, and the other side is blank. The top card shows $1$ , the next one shows $2$ , and so on down to the bottom card, which shows $n$ . Initially every card lies with its number facing up.

Archibald performs $m$ turns. On the $i$ -th turn he lifts the top $k_i$ cards, flips this whole group upside down as a single block (their order is reversed and every card is turned over), and puts the group back on top of the pack.

After all $m$ turns are finished, determine the final position and orientation of several chosen cards.

Input

The first line contains two integers $n$ and $m$ , separated by a space ( $1 \le n \le 100000$ , $1 \le m \le 1000$ ): the number of cards and the number of turns.

Each of the next $m$ lines contains one integer $k_i$ ( $1 \le k_i \le n$ ): the number of top cards flipped on that turn.

The next line contains one integer $s$ ( $1 \le s \le 10000$ ): the number of queries.

Each of the next $s$ lines contains one integer: the number written on a card whose final position and orientation must be reported.

Output

Print exactly $s$ lines. For the $j$ -th query, let $p$ be the final position of that card counted from the top (the top card is position $1$ ). Print $+p$ if the card's number ends up facing up, or $-p$ if it ends up facing down.

Examples4

Example 1
Input
```
8 3
1
8
4
5
4
8
1
5
2
```
Expected output
```
-5
+4
+8
+1
-7
```
Example 2
Input
```
5 1
5
5
1
2
3
4
5
```
Expected output
```
-5
-4
-3
-2
-1
```

Example 3

Input

Expected output

-4
+1
+5
+6
+2
+3

Example 4

Input

Expected output

-3
-10
-5
-1
+4
-9