408773: GYM103306 H Haunted House

Haunted houses are one of the most popular Halloween attractions. Bob plans to open his own haunted house for Halloween this year. His haunted house consists of $$$N$$$ rooms numbered from $$$0$$$ to $$$N-1$$$.

Bob has $$$N$$$ ghosts and each of them has a unique energy value between $$$1$$$ and $$$N$$$. A ghost with energy $$$x$$$ can be active for $$$x$$$ consecutive seconds, and then it needs to rest for $$$x$$$ seconds until it can be active again. But there is one more flaw, if that ghost scares a person while it's active, then it needs to rest immediately for $$$x$$$ seconds until it can be active again, since scaring people is tiring for ghosts.

Before deciding where to place the ghosts, Bob wants to simulate some scenarios. A scenario is defined by a permutation $$$p_0, p_1, \dots, p_{N-1}$$$, indicating that Bob places a ghost with energy $$$p_i$$$ in the room $$$i$$$, and a sequence $$$t_0, t_1, \dots, t_{M-1}$$$, indicating the arriving time of people to the haunted house.

If a person arrives to the house at second $$$t_j$$$, then they visit the cell $$$0$$$ at second $$$t_j$$$. When a person visits the cell $$$i$$$ at second $$$T$$$, there are two cases:

1. If there is an active ghost in the room, then the person gets scared and abandons the house immediately. The ghost starts resting at second $$$T+1$$$.
2. Otherwise, the person visits to the room $$$i+1$$$ at second $$$T+1$$$ or abandons the house if $$$i+1=N$$$.

You are given a scenario, help Bob to simulate it and find what is the room where the people get scared and the second when that happens. Note that all ghosts start being active at second $$$0$$$.

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 10^5$$$). The second line contains a permutation $$$p_0, p_1, \dots, p_{N-1}$$$ of size $$$N$$$ ($$$1 \leq p_i \leq N$$$), indicating that a ghost with energy $$$p_i$$$ is placed in room $$$i$$$. The third line contains $$$M$$$ integers $$$t_0, t_1, \dots t_{M-1}$$$ ($$$0 \leq t_i \leq 10^5$$$), the second when the people arrive to the house. All people arrive at different time.

Print $$$M$$$ lines. In the $$$j$$$-th line print two space-separated integers: the number of the room where the person with number $$$(j-1)$$$ get scared and the second when they get scared. If the person abandons the house without being scared in any room, print two $$$-1$$$ separated by a space.

2 3
2 1
0 2 5

0 0
-1 -1
1 6

3 3
3 1 2
0 4 10

0 0
0 4
0 10