People in Nloglônia are very addicted to video games as they spend hours playing every day. As they are a very competitive community, everyone competes to see who has more gaming achievements or trophies. Every time someone starts a new game, they spend some time playing the single player portion of the game, but what they really like is the multiplayer.

There's a game that became very famous in the city involving some assassins and their creed. Anyway, the objective of the multiplayer game is to hunt and assassinate others assassins. The player's skill is measured by how much experience (XP) he has, which can be accumulated by doing various actions in the game, i.e. killing or poisoning a target, running away from who wants to kill you or stunning someone, and so on.

But there's a problem, everyone wants to complete the game as fast as they can, in order to start a new one. To complete this game, there's an achievement that's obtained when a player reaches X experience points. You possibly need to play a lot of multiplayer rounds to reach that amount of XP, and that's why a group of friends decided to boost their XP, it consists of helping everybody in the group to reach a desired amount as fast as possible.

Here's how this match goes. There are always 6 players separated in 3 teams with 2 players each. Let's give each player an identifier from 1 through 6, and assume that the teams are organized as follows: players 1 and 2 in the first team, players 3 and 4 in the second team, and players 5 and 6 in the third team. The game is separated in rounds, each taking 4 minutes to complete.

To boost their experiences, the players agreed that an easy and fast way to do it is through the stun boosting. This boosting method consists of stunning each other instead of killing. It's true that killing will give you more XP points, but the dead player end up spending too much time to respawn and to meet with the someone else again. The boosting will happens as follows. Everyone must meet at the center of the map to start stunning each other. Two groups with one player from each team will be formed in this location. The players takes different amount of time to reach the center of the map (depending on where they first spawned) so the group that reaches the center first will start boosting first. If both players from the same team gets to the center at the same time, the one with lower identifier must be chosen to be part of the first group.

As soon as a group meet at the center of the map they start stun boosting. Every time a player gets stunned he lands on the ground for some time, and then gets up. A stun round consists of all players in the group stunning and getting stunned. An example of a stun round:

player 1 stuns player 2, player 3 stuns player 1, player 2 waits to get up and stuns player 3. In this problem, a stun round takes 7 seconds. This happens over and over until the round is over.

If this wasn't enough, the players are following these two guidelines that they created to raise the experience even faster, and be as fair as possible with everyone in the group. First, if two players from opposing teams meet up at the center, they must wait for the third one to come, and then start boosting (they hold still until the group has three members). Second, if they know there's no time left in the round to complete a stun round, they will not do it, instead, if there's 2 or more seconds remaining they have time to poison each other, getting some extra and welcome XP.

For each stun the player gets 300XP, and for each poison kill the player gets 1800XP. Note that the XP earned stunning will be granted to the player at the end of the stun round (that takes 7 seconds) and the XP earned poisoning will be granted in the end of the 4 minutes round. Also, you must note that when poisoning, the three players are able to poison someone else because it takes some time for it to really kill them. The players will choose to poison each other if and only if there's no time left for a stun round (even though poisoning should work better to raise the experience).

You are given the amount of XP the players want to reach, the number of rounds they played and the initial amount of experience the players had before starting boosting. For each round, you are given the time that each player takes to reach the center of the map. The players want to know who was the player that reached the experience goal first, and in which round he did. If no player reached the goal, they want to know the experience of everyone after they played all the rounds.

Input

The input contains several test cases. The first line of a test case contains two integers, X and R (1 ≤ X ≤ 650000, 1 ≤ R ≤ 1000), which represents the amount of experience the players want to achieve and the number of rounds they played, respectively.

The second line of a test case contains six integers X_i (1 ≤ i ≤ 6) that represents the initial experience of the i^th player. Then R lines follows, each containing six integers T_i (1 ≤ i ≤ 6; 0 < T_i < 240) representing the time that the i^th player reached the center of the map on that round.

The end of the input is marked by X = R = 0.

Output

For each test case your program should output one line. If some player reached the desired experience, you should output two integers indicating the identifier of the first player to reach the desired experience, and the numbers of rounds necessary to this player to do so. If more than one player reached the desired experience at the same time, output the one with lower identifier. In the case that no player reached the desired experience, you should output "-1" and then six integers containing the amount of experience each player had after playing all the rounds.

Example

Input:
10000 1
1000 12345 50000 9000 100 1
30 10 20 20 10 30
650000 1
100 200 300 400 500 600
20 10 30 20 20 30
0 0

Output:
2 0
-1 9100 11300 9300 11500 11600 9600