B. The Moon golf
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While visiting the Moon, Neznayika discovered an absolutely new game like Earth's golf. In the Moon golf, the same as Earth's type, one needs to score balls in holes. However, holes are replaced by craters and balls – by meteorites.

Meteorites have different masses. The player's task is to score meteorites to the craters so that the total mass of the scored meteorites is the highest. The rules prohibit scoring more than one meteorite in one crater.

According to the rules of the Moon golf:

  1. a player is always situated in point $$$(0, 0)$$$;
  2. craters are perfect circles;
  3. when a meteorite doesn't score into the center of the crater but falls at least at its border – meteorite inevitably rolls into the center and is considered scored;
  4. craters do not overlap or touch each other;
  5. the point $$$(0, 0)$$$, where a player is situated, isn't inside the crater.

The powers of Neznayika are not endless, so the maximum distance he can reach with a meteorite depends on the mass $$$m$$$ of this meteorite and is calculated by the formula $$$ d = \sqrt{10^6 / m}$$$.

Help Neznayika to win – write a program that, using coordinates of craters and meteorite mass, determines the game's optimal strategy. For simplicity, let us assume that Neznayika does not know how to miss, and the strategy simply describes which meteorite should be scored into which crater.

Input

In the first line is given an integer $$$ n $$$ $$$( 1 \leq n \leq 10^4 )$$$ – the number of meteorites. The second line consists of $$$n$$$ integers $$$ w_i $$$ $$$( 1 \leq w_i \leq 10^6 )$$$ separated by spaces – the mass of the meteorites.

The third line consists of the integer $$$ k $$$ $$$( 1 \leq k \leq 10^5 )$$$ – the number of craters on the playing field. In the next $$$k$$$ lines, there are triples of integers $$$ x_i , y_i, r_i $$$ $$$( -2\,000 \leq x_i, y_i \leq 2\,000 $$$, $$$ 1 \leq r_i \leq 10 )$$$ separated by spaces – coordinates of craters'centers and their radiuses.

Output

The first line should contain an integer $$$ r $$$ $$$( 0 \leq r \leq min(n, k))$$$ – the number of meteorites that are supposed to be scored. Then $$$r$$$ lines, each containing two integer numbers $$$ s_i $$$ $$$(1 \leq s_i \leq n )$$$ and $$$ t_i $$$ $$$( 1 \leq t_i \leq k )$$$ – the number of the meteorite and the number of the crater where it should be scored. Meteorites and craters are numbered in the order of appearance in the input data. Numbering starts with one.

Examples
Input
3
1 100 10000
3
0 10 1
0 100 1
0 1000 1
Output
3
1 3
2 2
3 1
Input
2
2 3
2
1000 0 1
0 1000 1
Output
0