Hide-and-seek

You got your hands on a TV game released by JOI Company. It was a fairly well-made game, and you played it every day, enjoying it in your own way.

One day, a stage called "hide-and-seek" appeared among gamers. Apparently the stage has a bug, and even skilled gamers can clear it only with a very small probability.

While challenging that stage many times, you realized that with very fast judgment there might be a chance to clear it, and you thought you could handle it by writing a program.

The hide-and-seek stage takes place in a location with many obstacles. The stage is rectangular and divided into 1 × 1 square cells. Each cell is represented as (x, y) by integers x, y satisfying 1 ≤ x ≤ 100,000 and 1 ≤ y ≤ 1,000,000,000. (1, 1) is the top-left cell, and (x + 1, y + 1) represents the cell reached from (1, 1) by moving x to the right and y downward.

Each obstacle is placed on w consecutive cells with the same y coordinate. That is, an obstacle looks like a rectangle occupying w × 1 cells. One obstacle is represented by the pair of the coordinates (x, y) of the cell with the smallest x coordinate among them and the length w. Obstacles are placed on cells with 2 ≤ y. Obstacles do not overlap each other.

When the stage begins, the player moves around the stage. The player can move to any cell, including cells with obstacles.

After a certain amount of time, an enemy appears and attacks. At this point the player must hide inside an obstacle. To hide inside an obstacle, it is enough to be on a cell with that obstacle. By hiding inside a suitable obstacle, the player avoids the attack and gets a chance to counterattack the enemy. By using that chance, the stage can be cleared.

The enemy has M kinds of weapons (for example, handguns, rifles, recoilless rifles, electromagnetic launchers, and so on). Weapons have unique numbers from 1 to M, and weapon i has attack power ai. The attack power means that the weapon can destroy that many obstacles.

If the player is hiding inside a destroyed obstacle, the player takes damage.

The enemy was supposed to appear at (x, 1) using a randomly chosen x and attack downward with a randomly chosen weapon. However, due to a bug in the game, the enemy always chooses the x coordinate where the player is and attacks toward the player.

Using a program you wrote yourself, you decided to find, for each weapon, the optimal hiding place where the player avoids the attack no matter which weapon the enemy uses. The optimal hiding place is the one with the smallest y coordinate, so that the player can counterattack easily. Also, if there are multiple such places, the one with the smallest x coordinate among them is optimal.

Given the obstacle information and the attack power of each weapon, write a program that finds the optimal hiding place for each weapon the enemy has. However, if the player takes the attack no matter how they hide, output (-1,-1), meaning there is no hiding place.

Figure 1: A way of hiding corresponding to a weapon with attack power 4

Read the following input from standard input.

• Line 1 contains integers N and M separated by a space.
• Of the following N lines, line i contains integers xi, yi, wi separated by spaces.
• Of the following M lines, line j contains an integer aj.

Output the following data to standard output.

• The data consists of M lines. Line j contains two integers xj and yj separated by a space, meaning that the coordinates of the optimal hiding place corresponding to weapon j are (xj, yj). If the player takes the attack of weapon j no matter how they hide, set xj = yj = −1.

• 1 ≤ N ≤ 50,000 number of obstacles
• 1 ≤ M ≤ 50,000 kinds of weapons
• 1 ≤ xi ≤ 100,000 smallest x coordinate among the cells where obstacle i is placed
• 2 ≤ yi ≤ 1,000,000,000 y coordinate of obstacle i
• 1 ≤ wi + xi − 1 ≤ 100,000 wi is the length of obstacle i
• 1 ≤ aj ≤ N attack power of weapon j