1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// XDDDDDDDDDDDDDDDDDd
// xd.
#include <bits/stdc++.h>
using namespace std;
#define x_d for
#define X_D(dd, ddd, dddd) x_d(int dd = ddd; dd < dddd; ++dd)

#define xDD tie
#define x first
#define d second
#define xxxddd 100001
#define dddxxx 4
#define xdxdxdxd 0x3f3f3f3f
#define xDd int
#define XdD void
#define xDDx auto
#define xddddd if
#define xdddddd while
#define x6 memset

map<tuple<xDd, xDd, xDd>, xDd>xdd;
queue<tuple<xDd, xDd, xDd>>xddd;
xDd XDDDD[xxxddd];


XdD XDD(XdD) {
	x6(XDDDD, xdxdxdxd, xxxddd * dddxxx);
	xDd XD[(dddxxx) - (dddxxx / dddxxx)], xd[(dddxxx) - (dddxxx / dddxxx)], dx[(dddxxx) - (dddxxx / dddxxx)];
	scanf("%d%d%d%d%d%d", &XD[dddxxx - dddxxx], &XD[dddxxx / dddxxx], &XD[dddxxx >> (dddxxx / dddxxx)], &xd[dddxxx - dddxxx], &xd[dddxxx / dddxxx], &xd[dddxxx >> (dddxxx / dddxxx)]);
	xdd[xDD(xd[dddxxx - dddxxx], xd[dddxxx / dddxxx], xd[dddxxx >> (dddxxx / dddxxx)])] = dddxxx - dddxxx;
	xddd.push(xDD(xd[dddxxx - dddxxx], xd[dddxxx / dddxxx], xd[dddxxx >> (dddxxx / dddxxx)]));
	
	xdddddd(!xddd.empty()) {
		xDD(xd[dddxxx - dddxxx], xd[dddxxx / dddxxx], xd[dddxxx >> (dddxxx / dddxxx)]) = xddd.front();
		xddd.pop();
		X_D(_x_d_, dddxxx - dddxxx, dddxxx - (dddxxx / dddxxx))
		X_D(_d_x_, dddxxx - dddxxx, dddxxx - (dddxxx / dddxxx))
			xddddd(_x_d_ != _d_x_) {
				xDd xD = min(xd[_x_d_], XD[_d_x_] - xd[_d_x_]);
				memcpy(dx, xd, dddxxx + dddxxx + dddxxx);
				dx[_x_d_] -= xD;
				dx[_d_x_] += xD;
				xDDx dxx = xDD(dx[dddxxx - dddxxx], dx[dddxxx / dddxxx], dx[dddxxx >> (dddxxx / dddxxx)]);
				xddddd(xdd.find(dxx) == xdd.end()) {
					xdd[dxx] = xdd[xDD(xd[dddxxx - dddxxx], xd[dddxxx / dddxxx], xd[dddxxx >> (dddxxx / dddxxx)])] + dddxxx / dddxxx;
					xddd.push(dxx);
				}
			}	
	}
	x_d(xDDx xxdd : xdd) {
		xDD(xd[dddxxx - dddxxx], xd[dddxxx / dddxxx], xd[dddxxx >> (dddxxx / dddxxx)]) = xxdd.x;
		x_d(xDDx xdxd : xd)
			XDDDD[xdxd] = min(XDDDD[xdxd], xxdd.d);
	}
	
	X_D(xdxd, dddxxx - dddxxx, XD[dddxxx >> (dddxxx / dddxxx)] + dddxxx / dddxxx)
		printf("%d ", XDDDD[xdxd] == xdxdxdxd ? - dddxxx / dddxxx : XDDDD[xdxd]);
}


xDd main(XdD) {
	XDD();
}