K. Uau Aiai
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There's a timber wood company that spans several countries. Associated with the company, there are $$$N_0$$$ countries, numbered from $$$0$$$ to $$$N_0-1$$$. In total, there are $$$N_0N_1$$$ cities, numbered from $$$0$$$ to $$$N_0N_1-1$$$ such that city $$$x$$$ belongs in country $$$\lfloor\frac{x}{N_1}\rfloor$$$. In total, there are $$$N_0N_1N_2$$$ locations that the company operates in. These locations are numbered from $$$0$$$ to $$$N_0N_1N_2-1$$$ such that location $$$x$$$ belongs in city $$$\lfloor\frac{x}{N_2}\rfloor$$$.

There is a truck driver who has to drive her truck carrying wood logs around all $$$N_0N_1N_2$$$ locations. The truck must start in any one of these locations, then go to every single one of the other locations any order, then end the journey in any location. She can visit a location more than once.

Since the truck driver likes to pee carelessly wherever she goes, there is an additional restriction to the entire journey. For each city, once the truck leaves the city, it can't go back into that city. The same thing applies to each country. Once the truck leaves a country, it can't go back into that country.

There are three different fees, denoted by three functions $$$f$$$, $$$g$$$, and $$$h$$$, each with two parameters.

  • The values of $$$f(x,y)$$$ are defined for all $$$0\leq x \lt y\leq N_0-1$$$.
  • The values of $$$g(x,y)$$$ are defined for all $$$0\leq x \lt y\leq N_0N_1-1$$$.
  • The values of $$$h(x,y)$$$ are defined for all $$$0\leq x \lt y\leq N_0N_1N_2-1$$$.

For any pair $$$(x,y)$$$ ($$$x \lt y$$$), when the driver wants to drive her truck directly from location $$$x$$$ to location $$$y$$$ or vice versa, she must do all of the following three things:

  • If $$$x$$$ and $$$y$$$ are in different countries, she must pay $$$f(\lfloor\frac{x}{N_1N_2}\rfloor,\lfloor\frac{y}{N_1N_2}\rfloor)$$$ gold coins.
  • If $$$x$$$ and $$$y$$$ are in different cities, she must pay $$$g(\lfloor\frac{x}{N_2}\rfloor,\lfloor\frac{y}{N_2}\rfloor)$$$ silver coins.
  • She must pay $$$h(x,y)$$$ bronze coins.

There are some special properties for the values of functions $$$f$$$ and $$$g$$$.

  • For any pair of pairs $$$(x,y)$$$ and $$$(x',y')$$$ ($$$x \lt y$$$; $$$x' \lt y'$$$; $$$(x,y)\neq(x',y')$$$), if $$$f(x,y)\leq f(x',y')$$$ holds, then $$$2f(x,y)\leq f(x',y')$$$ also holds.
  • For any pair of pairs $$$(x,y)$$$ and $$$(x',y')$$$ ($$$x \lt y$$$; $$$x' \lt y'$$$; $$$(x,y)\neq(x',y')$$$), if $$$\lfloor\frac{x}{N_1}\rfloor=\lfloor\frac{y}{N_1}\rfloor=\lfloor\frac{x'}{N_1}\rfloor=\lfloor\frac{y'}{N_1}\rfloor$$$ holds and $$$g(x,y)\leq g(x',y')$$$ holds, then $$$2g(x,y)\leq g(x',y')$$$ also holds.
  • For any pair of pairs $$$(x,y)$$$ and $$$(x',y')$$$ ($$$x \lt y$$$; $$$x' \lt y'$$$; $$$(x,y)\neq(x',y')$$$), if $$$\lfloor\frac{x}{N_2}\rfloor=\lfloor\frac{y}{N_2}\rfloor=\lfloor\frac{x'}{N_2}\rfloor=\lfloor\frac{y'}{N_2}\rfloor$$$ holds and $$$h(x,y)\leq h(x',y')$$$ holds, then $$$2h(x,y)\leq h(x',y')$$$ also holds.

Gold coins are way more valuable than silver coins, and silver coins are way more valuable than bronze coins. Let's say the total gold, silver, and bronze coins of the entire journey are denoted as $$$p$$$, $$$q$$$, and $$$r$$$. Find the lexicographically minimum array $$$[p,q,r]$$$!

Input

The first line contains three integers $$$N_0$$$, $$$N_1$$$, and $$$N_2$$$ ($$$2 \leq N_0 \leq 11$$$; $$$2 \leq N_1 \leq 10$$$; $$$2 \leq N_2 \leq 9$$$) — the number of countries, the number of cities in each country, and the number of locations in each city.

The $$$i$$$-th of the next $$$N_0-1$$$ lines contains $$$N_0-i$$$ integers $$$f(i-1,i),f(i-1,i+1),f(i-1,i+2),\ldots,f(i-1,N_0-1)$$$ ($$$1\leq f(x,y)\leq10^{17}$$$) — the gold coin costs for travelling between different countries.

The $$$i$$$-th of the next $$$N_0N_1-1$$$ lines contains $$$N_0N_1-i$$$ integers $$$g(i-1,i),g(i-1,i+1),g(i-1,i+2),\ldots,g(i-1,N_0N_1-1)$$$ ($$$1\leq g(x,y)\leq10^{16}$$$) — the silver coin costs for travelling between different cities.

The $$$i$$$-th of the next $$$N_0N_1N_2-1$$$ lines contains $$$N_0N_1N_2-i$$$ integers $$$h(i-1,i),h(i-1,i+1),h(i-1,i+2),\ldots,h(i-1,N_0N_1N_2-1)$$$ ($$$1\leq h(x,y)\leq10^{15}$$$) — the bronze coin costs for travelling between different locations.

For any pair of pairs $$$(x,y)$$$ and $$$(x',y')$$$ ($$$x \lt y$$$; $$$x' \lt y'$$$; $$$(x,y)\neq(x',y')$$$), if $$$f(x,y)\leq f(x',y')$$$ holds, then $$$2f(x,y)\leq f(x',y')$$$ also holds.

For any pair of pairs $$$(x,y)$$$ and $$$(x',y')$$$ ($$$x \lt y$$$; $$$x' \lt y'$$$; $$$(x,y)\neq(x',y')$$$), if $$$\lfloor\frac{x}{N_1}\rfloor=\lfloor\frac{y}{N_1}\rfloor=\lfloor\frac{x'}{N_1}\rfloor=\lfloor\frac{y'}{N_1}\rfloor$$$ holds and $$$g(x,y)\leq g(x',y')$$$ holds, then $$$2g(x,y)\leq g(x',y')$$$ also holds.

For any pair of pairs $$$(x,y)$$$ and $$$(x',y')$$$ ($$$x \lt y$$$; $$$x' \lt y'$$$; $$$(x,y)\neq(x',y')$$$), if $$$\lfloor\frac{x}{N_2}\rfloor=\lfloor\frac{y}{N_2}\rfloor=\lfloor\frac{x'}{N_2}\rfloor=\lfloor\frac{y'}{N_2}\rfloor$$$ holds and $$$h(x,y)\leq h(x',y')$$$ holds, then $$$2h(x,y)\leq h(x',y')$$$ also holds.

Output

A single line containing three integers representing the lexicographically minimum array of the number of gold, silver, and bronze coins for the entire journey.

Example
Input
2 3 2
3
1 6 9 7 9
3 3 2 8
9 8 9
2 9
4
4 1 2 1 3 4 2 2 3 4 2
4 1 1 4 2 3 1 3 2 4
2 3 4 1 3 3 1 4 2
3 4 2 2 4 2 3 2
1 2 2 4 2 3 3
3 3 2 4 1 2
4 2 2 3 1
1 3 2 2
1 3 1
2 4
3
Output
3 16 21
Note

One possible optimal journey is as follows:

  • Start at location $$$10$$$.
  • Go to location $$$11$$$. Pay $$$3$$$ bronze coins.
  • Go to location $$$8$$$. Pay $$$4$$$ silver coins and $$$1$$$ bronze coin.
  • Go to location $$$9$$$. Pay $$$1$$$ bronze coin.
  • Go to location $$$8$$$. Pay $$$1$$$ bronze coin.
  • Go to location $$$7$$$. Pay $$$2$$$ silver coins and $$$1$$$ bronze coin.
  • Go to location $$$6$$$. Pay $$$4$$$ bronze coins.
  • Go to location $$$2$$$. Pay $$$3$$$ gold coins, $$$3$$$ silver coins, and $$$1$$$ bronze coin.
  • Go to location $$$3$$$. Pay $$$2$$$ bronze coins.
  • Go to location $$$1$$$. Pay $$$1$$$ silver coin and $$$1$$$ bronze coin.
  • Go to location $$$0$$$. Pay $$$4$$$ bronze coins.
  • Go to location $$$4$$$. Pay $$$6$$$ silver coins and $$$1$$$ bronze coin.
  • Go to location $$$5$$$. Pay $$$1$$$ bronze coin.

Total gold coins is $$$3$$$. Total silver coins is $$$4+2+3+1+6=16$$$. Total bronze coins is $$$3+1+1+1+1+4+1+2+1+4+1+1=21$$$.