A Compilation of Network Flow Graphs: from Beginner to Master

Link: https://codeforces.com/contest/653/problem/D

Niwel is a little golden bear. As everyone knows, bears live in forests, but Niwel got tired of seeing all the trees so he decided to move to the city.

In the city, Niwel took on a job managing bears to deliver goods. The city that he lives in can be represented as a directed graph with \(n\) nodes and \(m\) edges. Each edge has a weight capacity. A delivery consists of a bear carrying weights with their bear hands on a simple path from node \(1\) to node \(n\). The total weight that travels across a particular edge must not exceed the weight capacity of that edge.

Niwel has exactly \(x\) bears. In the interest of fairness, no bear can rest, and the weight that each bear carries must be exactly the same. However, each bear may take different paths if they like.

Niwel would like to determine the maximum amount of weight he can deliver (it is the sum of weights carried by bears). Find the maximum weight.

Input

The first line contains three integers \(n\), \(m\) and \(x\) (\(2 \le n \le 50\), \(1 \le m \le 500\), \(1 \le x \le 100,000\)) — the number of nodes, the number of directed edges and the number of bears, respectively.

Each of the following \(m\) lines contains three integers \(a_i\), \(b_i\) and \(c_i\) (\(1 \le a_i, b_i \le n\), \(a_i \neq b_i\), \(1 \le c_i \le 1,000,000\)). This represents a directed edge from node \(a_i\) to node \(b_i\) with weight capacity \(c_i\). There are no self loops and no multiple edges from one node to another. More formally, for each \(i\) and \(j\) with \(i \neq j\), it is guaranteed that \(a_i \neq a_j\) or \(b_i \neq b_j\). It is also guaranteed that there is at least one path from node \(1\) to node \(n\).

Output

Print one real value on a single line — the maximum amount of weight Niwel can deliver if he uses exactly \(x\) bears. Your answer will be considered correct if its absolute or relative error does not exceed \(10^{-6}\).

Namely: let us assume that your answer is \(a\), and the answer of the jury is \(b\). The checker program will consider your answer correct if \(\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}\).

Examples

Input

Output

Input

Output

Note

In the first sample, Niwel has three bears. Two bears can choose the path \[ 1 \to 2 \to 4, \] while one bear can choose the path \[ 1 \to 3 \to 4. \] Even though the bear that goes on the path \(1 \to 3 \to 4\) can carry one unit of weight, in the interest of fairness, he is restricted to carrying \(0.5\) units of weight. Thus, the total weight is \(1.5\) units overall. Note that even though Niwel can deliver more weight with just \(2\) bears, he must use exactly \(3\) bears on this day.

Source

IndiaHacks 2016 - Online Edition (Div. 1 + Div. 2)

Simply binary search the answer and run max flow to see if the maximum flow can be achieved.

Link: https://codeforces.com/gym/101981/problem/I

There are \(n\) heroes and \(m\) monsters living on an island. The monsters have become very vicious recently, so the heroes have decided to reduce their numbers. However, the \(i\)-th hero can only kill one monster from the set \(M_i\). Joe, the strategist, has \(k\) bottles of magic potion, each of which can buff one hero's power, allowing him to kill one additional monster. Since the potion is very powerful, a hero can only take at most one bottle of potion.

Please help Joe determine the maximum number of monsters that can be killed by the heroes if he uses the optimal strategy.

Input

The first line contains three integers \(n\), \(m\), \(k\) (\(1 \leq n, m, k \leq 500\)) — the number of heroes, the number of monsters, and the number of bottles of potion.

Each of the next \(n\) lines contains one integer \(t_i\), the size of \(M_i\), followed by \(t_i\) integers \(M_{i,j}\) (\(1 \leq j \leq t_i\)), the indices (1-based) of monsters that can be killed by the \(i\)-th hero (\(1 \leq t_i \leq m\), \(1 \leq M_{i,j} \leq m\)).

Output

Print the maximum number of monsters that can be killed by the heroes.

Examples

Input

Output

Input

Output

Source

2018 ACM-ICPC Asia Nanjing Regional Programming Contest

Observe that the only change in this problem is that we now have potions that allow heroes to match one more monster. In other words, a potion allows a hero to carry one point more flow.

Therefore, we add a potion node \(p\) to the original graph. We add an edge from \(s\) to \(p\) with capacity \(k\) (using at most \(k\) potions overall). We then add an edge from \(p\) to every \(u_i\) with capacity \(1\) (using at most one potion on \(u_i\)).

It is easy to see that the flow solution corresponds to the solution to the problem.

Link: https://www.luogu.com.cn/problem/P2762

Professor W is planning a series of space flights for the National Space Center. Each flight can perform a series of commercial experiments to generate profit. A set of potential experiments \( E = \{E_1, E_2, \dots, E_m\} \) has been identified, along with a set of instruments \( I = \{I_1, I_2, \dots, I_n\} \) required for these experiments. Each experiment \( E_j \) requires a subset of instruments \( R_j \subseteq I \).

The cost of configuring instrument \( I_k \) is \( c_k \) dollars. The sponsor of experiment \( E_j \) has agreed to pay \( p_j \) dollars for the experiment results. Professor W's task is to develop an efficient algorithm that selects which experiments to perform and which instruments to configure during one space flight in order to maximize the net profit. Here, the net profit is defined as the difference between total revenue from the experiments performed and the total cost of configuring the instruments.

Given the details about the experiments and instrument configurations, write a program to determine the experiment plan that maximizes net profit.

Input

The first line contains two positive integers \( m \) and \( n \) \( (1 \leq n, m \leq 50) \), where \( m \) is the number of experiments and \( n \) is the number of instruments. The next \( m \) lines describe the experiments. Each line begins with an integer representing the payment agreed upon by the experiment's sponsor, followed by the indices of the instruments required for that experiment. The last line contains \( n \) integers, representing the configuration costs for each instrument.

Output

The first line contains the indices of the selected experiments.
The second line contains the indices of the instruments to configure.
The last line contains the maximum net profit.

Examples

Input

Output

Source

24 Problems of Network Flow, Luogu

Add a node for every \(E_i\) and a node for every \(I_i\). Let us say that if \(E_i\) is with the source then we carry out the experiment, otherwise we don't. Similarly, if \(I_i\) is with the source then we buy the equipment, otherwise we don't.

1. Add an edge from \(s\) to \(E_i\) with capacity \(p_i\) (opportunity cost if we don't carry out the experiment).
2. Add an edge from \(I_i\) to \(t\) with capacity \(c_i\) (cost to buy equipment).
3. Add an edge from \(E_i\) to \(I_j\) with capacity \(\infty\) if \(E_i\) needs \(I_j\) (if \(E_i\) is being carried out we must have the equipment).

Link: https://www.luogu.com.cn/problem/P4313

Choosing between majoring in Arts or Sciences is a tough decision! (Although those who see this problem probably have never struggled with it.)

Student P's class is deciding between Arts and Sciences. His class can be represented by an \(n \times m\) grid, where each cell corresponds to a student's seat. Each student must choose either Arts or Sciences, with the following satisfaction values assigned based on their choice:

• If the student in row \(i\), column \(j\) chooses Arts, they receive a satisfaction value of \(\operatorname{art}_{i,j}\). If they choose Sciences, they receive a satisfaction value of \(\operatorname{science}_{i,j}\).
• If the student in row \(i\), column \(j\) chooses Arts, and all adjacent students (cells are adjacent if and only if they share a common side) also choose Arts, the student becomes even happier, gaining an additional satisfaction value of \(\operatorname{same-art}_{i,j}\).
• Similarly, if the student in row \(i\), column \(j\) chooses Sciences, and all adjacent students also choose Sciences, they gain an additional satisfaction value of \(\operatorname{same-science}_{i,j}\).

Student P wants to know how to choose subjects for everyone in the class so that the total satisfaction value is maximized. Determine this maximum possible value.

Input

The first line contains two positive integers \(n\) and \(m\).

• The next \(n\) lines each contain \(m\) integers, representing \(\operatorname{art}_{i,j}\).
• The following \(n\) lines each contain \(m\) integers, representing \(\operatorname{science}_{i,j}\).
• The next \(n\) lines each contain \(m\) integers, representing \(\operatorname{same-art}_{i,j}\).
• The final \(n\) lines each contain \(m\) integers, representing \(\operatorname{same-science}_{i,j}\).

Output

Output a single integer representing the maximum possible total satisfaction.

Input

Output

Notes

In the explanation, "1" represents choosing Arts, and "0" represents choosing Sciences. An optimal choice arrangement is:

\(n, m \leq 100\)

All input values are \(\leq 500\).

Source

24 Problems of Network Flow, Luogu

This is similar to the lightbulb problem. The difference is that, instead of paying for two different choices, now we pay an opportunity cost if (at most) 5 people's interests are different.

We can use the same analysis. Let us say that if a node \(c_{i,j}\) is with the source, the student choose art. Otherwise, they choose science.

1. Add an edge from \(s\) to \(c_{i,j}\) with capacity \(\operatorname{art}_{i,j}\) (opportunity cost for not choosing art).
2. Add an edge from \(c_{i,j}\) to \(t\) with capacity \(\operatorname{science}_{i,j}\) (opportunity cost for not choosing science).
3. For every student create a node \(c^*_{i,j}\) indicating everyone around them choosing art — if it is with the source, then it is true, and we don't pay the opportunity cost. Therefore, connect \(s\) to \(c^*_{i,j}\) with capacity \(\operatorname{same-art}_{i,j}\). Connect \(c^*_{i,j}\) to every related student \(c_{k,l}\) with capacity \(\infty\).
4. Do the same for science, except in reverse.

Link: https://www.luogu.com.cn/problem/P2774

You are given an \(m \times n\) grid where each cell contains a positive integer. The task is to select numbers from the grid so that no two selected numbers are in adjacent cells (two cells are adjacent if they share a common side), and the sum of the selected numbers is maximized. Calculate this maximum sum.

Input

The first line contains two integers separated by a space, representing the number of rows \(m\) and columns \(n\) of the grid.

Each of the next \(m\) lines contains \(n\) integers. The \(j\)-th integer in the \((i+1)\)-th line represents the number \(a_{i,j}\) in the cell at row \(i\) and column \(j\).

Output

Output a single integer representing the maximum achievable sum.

Examples

Input

Output

Notes

For \(100\%\) of the data: \(1 \leq n, m \leq 100\), and \(1 \leq a_{i,j} \leq 10^5\).

Source

24 Problems of Network Flow, Luogu

Observe that the difference between this problem and the lightbulb one is that we cannot both pick squares at the same time. To counter this, 2-color the grid, and the rest is the same as the lightbulb.

Specifically, for the white cells, we say that we pick it if it is with the source; for the black cells, we say that we pick it if it is with the sink. We add a node \(c_{i,j}\) for every cell, then

1. Add an edge from \(s\) to every white \(c_{i,j}\) with capacity \(a_{i,j}\) (opportunity cost of not picking the cell).
2. Add an edge from every black \(c_{i,j}\) to \(t\) with capacity \(a_{i,j}\) (opportunity cost of not picking the cell).
3. Add an edge from neighboring white \(c_{i,j}\) to black \(c_{k,l}\) with capacity \(\infty\) (cannot pick both neighboring cell).

Link: http://hihocoder.com/problemset/problem/1252

In recent years, many free-to-play games, referred to as Kejin games, have emerged. These games are accessible without charge, but specific items or characters require payment. Examples include Love Live, Kankore, Puzzle & Dragon, Touken Ranbu, and Kakusansei Million Arthur, all of which have gained immense popularity and generate significant revenue daily.

In a Kejin game, your character possesses a skill graph that determines how skills can be acquired. This graph is a directed acyclic graph where vertices represent skills, and edges indicate dependencies: if there is an edge from skill A to skill B, A is a prerequisite for B. In cases where skill S has multiple dependencies, all must be acquired before obtaining S. Furthermore, each edge in the graph is unique, and cyclic dependencies are absent.

Acquiring skills typically involves time and effort, especially for advanced skills deeper in the graph. However, as a player with resources to spare, you can choose to pay money, denoted as "Ke," to bypass certain restrictions. Specifically, money can be used to remove edges from the dependency graph or to acquire skills directly, ignoring existing dependencies.

Given the constraints of time and money, you wish to optimize the balance between them. Each action, be it acquiring a skill through conventional means, removing an edge, or directly purchasing a skill, incurs a cost measured in units of "TA." You seek to determine the minimal cost required to acquire a desired skill S, starting without any initial skills.

Input

The input starts with an integer indicating the number of test cases (no more than 10). Each test case consists of:

• The first line containing three integers \(N\), \(M\), and \(S\), where \(N\) is the number of vertices (skills), \(M\) is the number of arcs (dependencies), and \(S\) is the index of the target skill (1-based index).
• \(M\) subsequent lines each contain three integers \(A\), \(B\), and \(C\), where there is an arc from skill \(A\) to skill \(B\) with \(C\) TAs cost to remove the dependency.
• A line with \(N\) integers representing the cost to acquire each skill through normal means.
• Another line with \(N\) integers representing the cost to directly acquire each skill via payment, bypassing any dependencies.

The costs for acquiring skills or removing dependencies range up to \(1,000,000\).

Output

For each test case, output a single line containing the minimal cost to acquire the specified skill \(S\).

Examples

Input

Output

Source

2015 ACM-ICPC Asia Beijing Regional Contest

For every skill, we build a path from \(s\) to \(t\) that goes through two nodes \(v_{i,1}\) and \(v_{i,2}\), where

1. if both \(v_{i,1}\) and \(v_{i,2}\) are with the source, we are not learning the skill
2. if \(v_{i,1}\) is with the source but \(v_{i,2}\) is with the sink, we are learning it directly
3. if both \(v_{i,1}\) and \(v_{i,2}\) are with the sink, we are learning the skill through its prerequisite

Therefore, we add these edges:

1. For the skill we want to acquire, add an edge from \(v_{i,2}\) to \(t\) with capacity \(\infty\).
2. Add an edge from \(v_{i,1}\) to \(v_{i,2}\) with capacity (cost to learn directly).
3. Add an edge from \(s\) to \(v_{i,1}\) with capacity (cost to learn through normal means).
4. For every skill \(i\) depending on \(j\), add an edge from \(v_{j,2}\) to \(v_{i,1}\) with capacity (cost to erase the dependency) — if \(v_{i,1}\) is with the sink (we are learning \(i\) normally) but \(v_{j,2}\) is with the source (we are not learning \(j\)), then we need to pay the cost.

Link: https://www.luogu.com.cn/problem/P4496

In the year 2323, with rapid technological progress and increasing population pressure on Earth, humanity begins mass migration to Mars. Encouragingly, the first stage of the immigration project is a great success. Currently, \(N\) immigration stations have been established on Mars. The coordinates of the \(i\)-th existing immigration station are \((u_i, v_i)\).

However, a significant challenge emerges: deciding where to build additional immigration stations. Investigations show that \(M\) new immigration stations need to be constructed. It is known that the information flow between the original \(i\)-th station and the new \(j\)-th station is \(A_{i,j}\), and the information flow between the new stations \(j\) and \(k\) is \(B_{j,k}\). It is assumed that transferring one unit of information flow over one unit of distance costs \(1\). Distance is defined as the Manhattan distance. Specifically, the Manhattan distance between two points \((x_1, y_1)\) and \((x_2, y_2)\) is:

\[ \operatorname{ManhattanDist}((x_1, y_1), (x_2, y_2)) = |x_1 - x_2| + |y_1 - y_2| \]

Given the coordinates of the existing \(N\) stations and the matrices \(A\) and \(B\) representing information flows, determine the optimal coordinates for the new \(M\) stations so that the total cost of information transmission is minimized.

Input

The input file names are locate1.in~locate10.in.

• The first line contains two integers \(N\) and \(M\), denoting the number of existing immigration stations and the number of new immigration stations to build.
• The next \(N\) lines each contain two integers, representing the coordinates of the existing immigration stations.
• The following \(N\) lines each contain \(M\) integers, representing the information flow matrix \(A\) between existing and new stations.
• The final \(M - 1\) lines contain information flow matrix \(B\). The \(i\)-th of these lines contains \(M - i\) integers, and the \(j\)-th integer in this line represents \(B_{i,i+j}\).

Output

The output file names are locate1.out~locate10.out, each corresponding to their respective input files.

• The first line contains a single integer, representing the minimal total information transmission cost.
• The next \(M\) lines each contain two integers, where the \(i\)-th line gives the coordinates of the \(i\)-th new immigration station.

Examples

Input

Output

Notes

The problem only requires submitting output files, so time limit is more lenient.

For input files, \(1\le N, M\le 100\).

Source

China CTSC 2009

First, observe that the x-coordinates and the y-coordinates are independent from each other, so we can consider them separately. For simplicity, let us consider the x-coordinates.

Then, observe that every new station will be built on the x-coordinate of some existing station. Otherwise, we can shift the coordinate of the new station to some existing station nearby and the cost will drop.

Now we are making a decision to pick the x-coordinate for every new station from a list of existing stations. Let us first sort every existing station by their x-coordinate. Then, for every new station \(i\), create a list of nodes \(v_{i,0}, v_{i,1}, \cdots, v_{i,n}\), where a cut between \(v_{i,k}\) and \(v_{i,k+1}\) represents picking the \(k\)-th existing station as the coordinate for the \(i\)-th new station. We can compute the cost of communication between existing stations and the \(i\)-th new station and set it as the edge capacity.

Now we need to process the cost between new stations. The trick is to use a list of edges between \(v_{i,k}\) and \(v_{j,k}\) for every \((i,j,k)\). Observe that if we cut at \(v_{i,k}\) and \(v_{j,l}\) (thickened edges in the figure), every edge from \(v_{j,x}\) to \(v_{i,x}\) with \(x\in[k+1,l]\) will also need to be cut (thickened edges in the figure). Therefore, it suffice to make the capacity of every edge \((X_{k}-X_{k-1})B_{i,j}\), so that it sums over the range and gives us the total cost \((X_{l}-X_{k})B_{i,j}\).

Link: https://www.luogu.com.cn/problem/P1251

A restaurant needs a varying number of napkins each day over a span of \(N\) consecutive days. Suppose on day \(i\), the restaurant requires \(r_i\) napkins (\(i = 1, 2, \dots, N\)). To meet this demand, the restaurant can:

• Purchase new napkins, each costing \(p\) cents;
• Send used napkins to a fast laundry, which takes \(m\) days to wash one napkin at a cost of \(f\) cents each;
• Send used napkins to a slow laundry, which takes \(n\) days to wash one napkin (with \(n > m\)) at a cost of \(s\) cents each (with \(s < f\)).

At the end of each day, the restaurant must decide:

• How many dirty napkins to send to the fast laundry,
• How many to send to the slow laundry,
• How many to save and postpone washing.

Each day's demand must be satisfied by the napkins washed (from either laundry) plus newly purchased napkins available that day.

Design an algorithm that determines an optimal napkin usage plan over \(N\) days to minimize the total cost. Write a program to compute this minimal total expense.

Input

The input is provided via standard input:

• The first line contains a single positive integer \(N\), representing the number of days for the napkin planning.
• The second line contains \(N\) integers, representing the number of napkins needed each day.
• The third line contains five positive integers: \(p, m, f, n, s\), where:
  • \(p\) is the cost of buying one new napkin.
  • \(m\) is the number of days required by the fast laundry.
  • \(f\) is the cost for washing one napkin at the fast laundry.
  • \(n\) is the number of days required by the slow laundry.
  • \(s\) is the cost for washing one napkin at the slow laundry.

Output

Output a single integer representing the minimal total cost of napkin usage for the restaurant over \(N\) days.

Examples

Input

Output

Notes

• For \(100\%\) of the data,
  • \(1 \le N \le 2 \times 10^3\)
  • \(1 \le r_i \le 10^7\)
  • \(1 \le p, f, s \le 10^4\).

Source

24 Problems of Network Flow, Luogu

Alternatively, the problem can be read as we are supplied with \(r_i\) dirty napkins on day \(i\), and need to pay a debt of \(r_i\) clean napkins that are either bought or come from previous days through washing.

Based on this logic, we add a node \(d_i\) for dirty napkins and \(c_i\) for clean napkins.

1. Add an edge from \(s\) to \(d_i\) with capacity \(r_i\) and cost \(0\) (supplied with dirty napkins).
2. Add an edge from \(d_i\) to \(c_{i+m}\) with capacity \(\infty\) and cost \(f\).
3. Add an edge from \(d_i\) to \(c_{i+n}\) with capacity \(\infty\) and cost \(s\).
4. Add an edge from \(d_i\) to \(d_{i+1}\) with capacity \(\infty\) and cost \(0\) (postpone washing).
5. Add an edge from \(s\) to \(c_i\) with capacity \(\infty\) and cost \(p\) (buy napkins).
6. Add an edge from \(c_i\) to \(t\) with capacity \(r_i\) and cost \(0\).

Link: https://www.luogu.com.cn/problem/P3980

After the successful Olympic bid, Bubu, through tireless efforts, finally becomes the head of the Human Resources department at a company under the Olympic Organizing Committee. Right after taking office, Bubu faces a tough task: recruiting short-term volunteers for a new Olympic project. It has been estimated that the project will last for \(n\) days, and on day \(i\), at least \(a_i\) volunteers are required.

After some investigation, Bubu finds that there are \(m\) types of volunteers available for recruitment. Volunteers of type \(i\) can work continuously from day \(s_i\) to day \(t_i\), with a cost of \(c_i\) per person. To impress everyone at his new job, Bubu wants to recruit enough volunteers at the minimal possible cost — but this isn't his strong suit! Therefore, Bubu comes to you, asking for your help to design an optimal recruitment strategy.

Input

The first line contains two integers \(n, m\), representing the number of days the project will run and the number of volunteer types available for recruitment.

The second line contains \(n\) non-negative integers, representing the minimum number of volunteers required each day.

Each of the next \(m\) lines contains three integers \(s_i, t_i, c_i\), describing the available volunteer types as stated above. Assume that there is an unlimited supply of volunteers for each type. It is guaranteed that a feasible recruitment plan exists.

Output

Output a single integer representing the minimum total cost of your optimal recruitment plan.

Examples

Input

Output

Notes

• \(1 \leq n \leq 1000\)
• \(1 \leq m \leq 10000\)
• All other values mentioned in the problem description are guaranteed not to exceed \(2^{31} - 1\).

Source

China NOI 2008

To start with, let us model each day with a node \(d_i\) and imagine that we connect them in a line from source to sink with capacity \(\infty\) and cost 0. Observe that the maximum flow is \(\infty\) in this graph.

To model the daily needs of \(d_1\), let us change the capacity of the edge that flows to \(d_1\) to \((\infty-a_1)\). Observe that we have created a choke point and the maximum flow is reduced to \((\infty-a_1)\).

We model meeting the demand as restoring the maximum flow to \(\infty\). Towards that end, we model each type of volunteer as a bypass that allows flow to go around the chokepoint. More specifically, for volunteer type \((s,t,c)\), we add an edge from \(d_{s-1}\) to \(d_{t}\) with capacity \(\infty\) and cost \(c\).

Observe that this edge allows us to bypass chokepoints between \(d_{s}\) and \(d_{t}\) by paying \(c\) per unit — the same as hiring a volunteer of that type.

Let us consider a more direct approach to the problem. For every day we still create a node \(c_i\) for clean napkins and \(d_i\) for dirty napkins.

1. Add an edge from \(s\) to \(c_i\) with capacity \(\infty\) and cost \(p\) (buying napkins).
2. Add an edge from \(d_i\) to \(c_{i+f}\) and from \(d_i\) to \(c_{i+s}\) (washing napkins).
3. Add an edge from \(d_i\) to \(d_{i+1}\) with capacity \(\infty\) and cost 0 (postponing washing napkins).
4. Add an edge from \(d_{N}\) to \(t\) (used napkins).
5. Add an edge from \(c_i\) to \(d_i\) with forced flow \(r_i\) (using napkins) (thick lines in the figure).

Now let us consider what how do we transform edges with lower bounds to normal edges. To begin with, we add a super source \(s^*\) and a super sink \(t^*\). Observe that to "force" a flow of \(r_i\) from \(c_i\) to \(d_i\) is the same as drawing out \(r_i\) flow from \(c_i\) and injecting \(r_i\) flow into \(d_i\). Therefore, we add an edge from \(c_i\) to \(t^*\) with capacity \(r_i\) and cost 0. Similarly, we add an edge from \(s^*\) to \(d_i\) with capacity \(r_i\) and cost 0.

We want to run our maximum flow with source \(s^*\) and sink \(t^*\) so that every edge going out of \(s^*\) and going into \(t^*\) achieves full capacity, which means that all lower bounds are satisfied. However, we need to fix the original source \(s\) and sink \(t\), since they will have additional incoming/outgoing flows in the original graph. Therefore, we add an edge from \(t\) to \(s\) with capacity \(\infty\) and cost 0, allowing the flow in the original graph that goes out of \(s\) and into \(t\) to cycle back.

Now if we run the min-cost flow on this graph with source \(s^*\) and sink \(t^*\), we simutanously achieve max flow (which means all constraints are satisfied) and min cost (which means we spend the minimum amount of money). You will see that this graph is equivalent to the graph in the original solution.

Link: https://www.luogu.com.cn/problem/P4533

Bingbing has three toys: Pikachu, Winnie-Sun-Wukong, and Barbie. She doesn't know their exact weights (in NOI units), but she knows their approximate ranges:

Table 1: Initial weight range of the toys

These ranges are too vague; Bingbing wants to narrow them down.

Fortunately, Jiajia has an electronic balance scale. It can indicate not only if both sides weigh the same but also exactly how much heavier (or lighter) one side is compared to the other. The scale is large enough to place multiple toys on either side simultaneously.

Bingbing borrows the scale from Jiajia to determine the precise weights of each toy. To test Bingbing, Jiajia imposes a restriction: each toy can be placed on each side of the scale at most once. For example, if Pikachu was placed on the left side once, it cannot be placed there again. Bingbing agrees and performs two weighings as follows (the numbers show how much heavier the left side is compared to the right):

Pikachu (-1) Winnie-Sun-Wukong

Winnie-Sun-Wukong (1) Barbie

Based on these weighings and Table 1, the exact weights of the three toys can be determined to be precisely 3, 4, and 3 units respectively. Thus, the updated weight ranges are:

Table 2: Exact weight ranges after weighings

Bingbing will buy many more toys in the future and doesn't want to manually calculate the weights each time. Can you help her write a program to determine the most precise possible lower and upper bounds for each toy's weight?

Input

• The first line contains two integers, \(n\) and \(m\), representing the number of toys and the number of weighings.
• The second line contains \(2n\) integers; the \((2i-1)\)-th and \(2i\)-th numbers represent the initial lower and upper bounds of the weight of the \(i\)-th toy.
• The next \(m\) lines each describe a weighing:
• The first three integers are \(L\), \(R\), and \(D\), representing the number of toys on the left side, the number of toys on the right side, and the difference in weight (left side minus right side), respectively.
• The next \(L\) integers indicate the indices of toys placed on the left side.
• The next \(R\) integers indicate the indices of toys placed on the right side.

Note: Each toy is placed on each side at most once throughout all weighings.

Output

Output exactly \(2n\) integers: the \((2i-1)\)-th and \(2i\)-th integers are the refined minimum and maximum integer weights of the \(i\)-th toy. If there is no valid solution (which indicates the scale may be broken or data inconsistent), output only one integer \(-1\).

Example

Input

Output

Input

Output

Notes

Example 1 corresponds to the case described in the problem statement.

In Example 2, the three toys have initial weight ranges 1–5, 2–5, and 1–3. After one weighing (toys 1 and 2 on the left, toy 3 on the right, and the left side heavier by 1 unit), the refined ranges become 1–2, 2–3, and 2–3.

• \(3 \le n \le 200\)
• \(1 \le m \le 100\)
• All weights and weight differences are integers no greater than 20,000.

Source

China CTSC 2005

We model each measurement as a node \(v_i\). Observe that each toy has exactly one mesaurement \(v_l\) that it appears on the left and one measurement \(v_r\) that it appears on the right. Therefore, we can add an edge from \(v_l\) to \(v_r\) with capacity bound of the initial range.

Now we consider each node \(v_i\). Observe that the incoming flow and the outgoing flow are almost equal, except by the different between the two sides \(D_i\). Therefore, we either add an edge from \(s\) to \(v_i\) or from \(v_i\) to \(t\), depending on which side is heavier, with capacity \(D_i\).

Then, we can add our super source \(s^*\) and super sink \(t^*\), change the graph similar to the solution above, and do the max flow accordingly. If every outgoing edge from \(s^*\) achieves full capacity, we know that we have at least one solution. Otherwise, we have no solutions.

Now we want to find the possible range of each toy. To obtain the upper bound for one toy, observe that we simply need to remove \(s^*\) and \(t^*\), and then run a max flow with source \(v_l\) and sink \(v_r\) on the residual network obtained from the previous max flow, since in the original graph, the only path connecting \(v_l\) and \(v_r\) is exactly the edge represented by the toy, and we need to maximize this flow. To obtain the lower bound, we only need to run a max flow with source \(v_r\) and sink \(v_l\) instead.

To simplify coding, since every outgoing edge from \(s^*\) achieves full capacity, \(s^*\) will not interfere with our max flow, so we don't actually need to remove it. The same goes for \(t^*\).