Maximum flow in an undirected graph

Input

The input consists of one or more test cases. Each test case starts with a line containing the integer $n$ (2 \le n \le 100), representing the number of vertices in the graph. The following line contains three integers: $s$, $t$, and $c$, which denote the source vertex, the sink vertex, and the number of edges, respectively. After this, there are $c$ lines, each with three integers describing an edge: the two vertices it connects and its capacity, which is a non-negative integer not exceeding $1000$. Multiple edges between the same pair of vertices are allowed, but self-loops are not.

The input concludes with a dummy test case consisting of the single number $0$, which should be ignored.

Output

For each test case, output the magnitude of the maximum flow.

Examples