Background

In year 3077 of the Stellar Calendar, the city Astra, floating above a sea of clouds, is kept running by a vast ether energy network.

The network consists of $n$ energy nodes and $m$ one-way energy transmission pipes. Energy starts from the main reactor $s$ and is ultimately delivered to the city core $t$. Each pipe has its own capacity limit.

The central control system has already computed a set of maximum-energy transmission plans. To avoid energy circulating pointlessly in the network, all pipes carrying positive flow in this plan do not form a directed cycle.

However, an unexpected meteor shower damaged one of the pipes, reducing its capacity by exactly $1$.

The city core may shut down at any moment due to insufficient energy. You need to compute a new maximum flow after the pipe is damaged as fast as possible.

---

Description

Given a directed graph $G=(V,E),$

where:

• $|V|=n$, with nodes numbered $1,2,\ldots,n$;
• $|E|=m$, with edges numbered $1,2,\ldots,m$ in input order;
• $s$ is the source;
• $t$ is the sink;
• The $i$-th edge goes from $a_i$ to $b_i$ and has positive integer capacity $c_i$.

Also given is an integral flow $f$, where the $i$-th edge currently carries $f_i$ units of flow.

It is guaranteed that $f$ is a maximum $s$-$t$ flow in the original graph; that is, it satisfies:

1. $0\le f_i\le c_i$,

2. For every $v\notin \{s,t \}$, we have

   $$\sum_{(u,v)\in E}f_{(u,v)}=\sum_{(v,w)\in E}f_{(v,w)}. $$

In addition, the given flow is acyclic. That is, after keeping only the edges with $f_i>0$, the resulting directed graph contains no directed cycle.

Now, the capacity of the $p$-th edge is reduced by exactly $1$. The modified capacities are

$$c'_i= \begin{cases} c_i-1,&i=p,\\ c_i,&i\ne p. \end{cases} $$

Output any integral maximum flow in the modified network.

---

Input Format

The first line contains five integers: $n,\ m,\ s,\ t,\ p$, denoting the number of nodes, the number of edges, the source, the sink, and the index of the edge whose capacity is reduced, respectively.

The next $m$ lines each contain four integers: $a_i,\ b_i,\ c_i,\ f_i$, meaning that the $i$-th edge goes from node $a_i$ to node $b_i$, its original capacity is $c_i$, and the original maximum flow sends $f_i$ units of flow along this edge.

---

Output Format

This problem uses a Special Judge.

The first line outputs an integer $F'$, the maximum flow value in the modified network.

The second line outputs $m$ integers $f'_1,f'_2,\ldots,f'_m$, where $f'_i$ denotes the flow on the $i$-th edge in the modified maximum flow.

The flow you output must satisfy:

1. All $f'_i$ are integers;
2. $0\le f'_i\le c'_i$ for every edge;
3. Flow conservation holds at every node except $s$ and $t$;
4. The value of this flow equals $F'$;
5. $F'$ is the maximum flow value of the modified network.

If multiple valid answers exist, output any one of them.

The output new maximum flow is also required to be an acyclic flow.

---

Constraints

For all test data:

$$2\le n\le 2\times 10^5,$$ $$1\le m\le 2\times 10^5,$$ $$1\le s,t\le n,\qquad s\ne t,$$ $$1\le p\le m,$$ $$1\le c_i\le 10^9,$$ $$0\le f_i\le c_i.$$

It is guaranteed that:

• $a_i\ne b_i$;
• The input graph may contain parallel edges;
• The given flow $f$ is an integral maximum flow of the original graph;
• The directed graph formed by all edges with $f_i>0$ contains no directed cycle;
• The capacity of the $p$-th edge may become $0$ after the reduction;
• The maximum flow value after the modification does not exceed $2\times 10^{14}$.

---

Sample Input

5 6 1 5 4
1 2 2 2
1 3 2 1
2 3 1 0
2 4 2 2
3 4 2 1
4 5 3 3

Sample Output

3
2 1 1 1 2 3

---

Explanation

The value of the original maximum flow is $3$.

The $4$-th edge is

$$2\rightarrow 4,$$

and its capacity was reduced from $2$ to $1$. Therefore, of the two units of flow originally passing through this edge, one unit can no longer be delivered along the original route.

This one unit of flow can be rerouted as

$$2\rightarrow 3\rightarrow 4.$$

The adjusted edge flows are:

Edge ID	Pipe	New Capacity	New Flow
$1$	$1\rightarrow2$	$2$	$2$
$2$	$1\rightarrow3$		$1$
$3$	$2\rightarrow3$	$1$
$4$	$2\rightarrow4$
$5$	$3\rightarrow4$	$2$
$6$	$4\rightarrow5$	$3$

Thus, even with one pipe damaged, the network can still maintain a maximum flow with value $3$.