Bird Formation Battle Strength

In the mountain, every bird has a unique identifier and an inherent strength value (\(w\)). Initially, all \(n\) birds are gathered at the mountain top at point \((0,0)\). The bird king issues a command every second for a total of \(t\) seconds. Each command instructs bird \(v\) to move instantly to a new point \((x,y)\) (the coordinate system has its origin at the mountain top, and the unit is defined as a bird claw).

After each command (including the initial state at time \(0\)), the birds at the same position form a group. For any bird in a group with size \(\ge 2\>,

• The morale (\(M\)) of a bird is defined as the maximum \(w\) among other birds in the same position. (That is, a bird does not consider its own \(w\) value.)
• The unity (\(U\)) of a bird is defined as the number of other birds at the same position.

If a bird is alone at its location, both its morale and unity are \(0\).

Each bird's battle strength is defined as the product of the maximum morale and the maximum unity it achieved over all time instants from \(0\) to \(t\), i.e., \[ \text{Battle Strength} = \Big( \max_{0 \le \tau \le t} M(\tau) \Big) \times \Big( \max_{0 \le \tau \le t} U(\tau) \Big). \]

You are given \(n\), \(t\), the inherent strengths \(w_1, w_2, \ldots, w_n\) for the birds, and then \(t\) commands. Each command is of the form:

[ v\ x\ y ]

which means that the bird with identifier \(v\) (1-indexed) moves to the coordinate \((x,y)\). Birds that are not commanded retain their previous positions. Compute and output the battle strength for each bird in the order of their identifiers, separated by spaces.

inputFormat

The input is given as follows:

 n t
 w1 w2 ... wn
 v1 x1 y1
 v2 x2 y2
 ...
 vt xt yt

where \(n\) is the number of birds, \(t\) is the number of commands, \(w_i\) is the inherent strength of the \(i\)-th bird, and every command instructs bird \(v\) to move to coordinate \((x,y)\).

outputFormat

Output a single line with \(n\) integers. The \(i\)-th integer is the battle strength of the \(i\)-th bird. The battle strength is computed as the product of the bird's maximum morale and maximum unity achieved over all time instants from \(0\) to \(t\).

sample

3 3
5 3 10
1 1 1
2 1 1
3 1 1

20 20 10