174. Two Stacks in One Array

Challenge1000 ms256 MBSolved by 0%

Hold TWO stacks inside a single array of size n, using no other storage. Neither stack has a fixed capacity — the only limit is that together they must fit.

Read n, then q operations, one per line:

1 s x — push x onto stack s (s is 1 or 2); print Full if the array is full and ignore the push
2 s — pop from stack s and print the value, or Empty if that stack has none

Print one line per 2 operation, plus a line for each rejected push.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `-1000000 ≤ x ≤ 1000000`

Input

The first line contains an integer n, the size of the shared array. The second line contains an integer q, the number of operations. Each of the next q lines is one operation: - 1 s x — push x onto stack s, where s is 1 or 2 - 2 s — pop from stack s and print the value

Output

Print one line for each 2 operation — the value, or Empty — plus a line reading Full for each rejected push.

Input5 4 1 1 10 1 2 20 2 1 2 2

Output10 20

Noteuses both stacks independently

Input2 3 1 1 1 1 1 2 1 1 3

OutputFull

Notefills the array with ONE stack, so the third push is rejected

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution