403757: GYM101257 I K, Push.

Rawand is designing a new game she called K, Push. for the employees at Mixed Dimension.

In K, Push., a group of N players sit in a circle, and each player has a red button in front of them.

When the game starts, an empty array is displayed on a large screen behind the players, and every few seconds, a random integer v is inserted into the array after some random index i. The first integer is always inserted after index 0 i.e., it is always inserted at index 1.

The players must keep watching the screen, and each player should push his button only if he thinks there is an increasing sub-sequence of length K in the array. The first player to do so is declared the winner, and the game ends. On the other hand, if a player pushes his button and there is no increasing sub-sequence of length K in the array, that player loses and is automatically considered out of the game. The remaining players will continue playing until the game's time ends, in this case all players will lose, or until only one player remains in the game, in this case, that player is declared the winner.

Rawand cannot wait to start the game, but she needs some help implementing the game's system. Given a random list of game events, can you help Rawand by writing a software that selects the winner of K, Push. based on the list events?

The first line of input contains three integers, N (2 ≤ N ≤ 10⁵), K (1 ≤ K ≤ 10⁵) and E (1 ≤ E ≤ 2 × 10⁵), the number of players in a game instance, the size of the required increasing sub-sequence, and the number of events in the event list.

Each of the E lines that follow will contain an event with one of the following formats:

•  +  i v, where v (1 ≤ v ≤ 10⁵) is an integer that got inserted after the element with index i (0 ≤ i ≤ currentSize).
• p j, which denotes that player number j (1 ≤ j ≤ N) pushed his button.

It is guaranteed that there are no more than 10⁵ events of the first type.

It is possible that the last event in the log is of type  + , and it is guaranteed that losing players will not appear in the input after losing.

On a single line, print out the index of the first event at which a winner should be declared, also, print the number of that winner on the same line.

If there’s no such winner, output  - 1 on a single line.

4 4 11
+ 0 14
+ 0 9
p 1
+ 2 19
+ 1 11
p 4
+ 0 1
+ 2 10
p 2
+ 1 3
+ 6 16

6 4

2 6 9
+ 0 14
+ 0 9
+ 2 19
+ 1 11
p 1
+ 0 1
+ 2 10
+ 1 3
+ 6 16

5 2

A sub-sequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence {1, 5, 4} is a sub-sequence of {2, 1, 5, 3, 4, 9}.