0160. Data Transmission

Имя входного файла:	data.in
Имя выходного файла:	data.out
Ограничение по времени:	2 s
Ограничение по памяти:	32 megabytes

Recently one known microprocessor productioner has developed the new type of microprocessors that can be used in difficult mathematical calculations. The processor contains N so called nodes that are connected by M channels. Data organized in packets, pass from source node to target node by channels and are processed by the intermediate nodes.

Each node has its level that determines the type of work this node does. The source node has level 1 while the target node has level L. For data to be correctly processed each packet of it must pass in order all nodes with levels from 1 to L – that is, first it must be processed by the source node, after that by some node of level 2, so on, and finally by the target node.

Nodes can process as much data as they are asked to, however channels can only transmit the limited amount of data in a unit of time. For synchronization reasons, any data can only be transmitted from a node with level i to some node with level i+1 and cannot be transmitted between nodes which levels differ by more than one or from a node of higher level to a node of lower level. Nodes are so fast that they can process data packet immediately, so as soon as it reaches the node it is ready to be transmitted to the node of the next level.

No data should stall in any node and no node can produce its own data, so each unit of time the number of packets coming to any node except source and target, must be equal to the number of packets leaving this node.

The scheme of data transmission that satisfies the conditions provided is called the data flow. Data flow is called blocking if there is no way to increase the value of the data flow just increasing the amount of data passing by some channels (however, there may be the way to increase it, decreasing the amount of data for some channels and increasing for other ones).

Your task is to find some blocking data flow for the microprocessor given its scheme. Note, that you need not find the maximal possible data flow, just any blocking one.

Input file

The first line of the input file contains three integer numbers – N, M and L (2 ≤ N ≤ 1,500, 1 ≤ M ≤ 300,000, 2 ≤ L ≤ N). Let nodes be numbered from 1 to N. The second line contains N integer numbers, i-th of them is the level l_i of the i-th node (1 ≤ l_i ≤ L). Only one node has level 1, that is the source node, and only one node has level L – that is the target node.

Next M lines describe channels, each lines contains three integer numbers a, b and c – nodes connected by this channel and its capacity in packets per unit of time (1 ≤ a, b ≤ N, l_b = l_a + 1, 1 ≤ c ≤ 10⁶).

Two nodes can be connected by at most one channel.

Output file

Output the description of the data flow found. Output file must contain M lines, they must correspond to channels and contain the amount of data transmitted by the channel in a unit of time. Channels must be listed in the order they are specified in the input file.

Examples:

data.in	data.out
6 7 4 1 2 3 4 3 2 1 2 3 2 3 3 3 4 4 1 6 4 6 3 2 5 4 3 6 5 4	3 3 4 4 1 3 3

Источник: Petrozavodsk Summer 2003. Final Contest, Saturday, August 30
Автор: Andrew Stankevich

Обсудить       Отправить решение



Версия для печати