Minimum Transformation Cost

You are given a sequence \(x\) of length \(n\) and an integer \(a=p\). Each element \(x_i\) of the sequence has an associated cost sequence \(w_{i,1},w_{i,2},\dots,w_{i,k}\). In one operation, you can transform the current value \(a\) into any \(i\) (\(1\le i\le n\)); note that \(a\) may be transformed to its own index. Suppose you are performing the \(j\)-th operation. The cost of changing \(a\) into \(i\) is given by:

[ w_{i,j} + 2\times\Bigl(L - (x_a \mathbin{&} x_i)\Bigr), ]

where \(x_a\) is the value of the current element, \(x_i\) is the value of the target element, \(\&\) denotes the bitwise AND operation, and \(L\) is defined as

[ L = \max_{1\le i\le n} x_i. ]

Your task is to determine, for every \(1\le i\le n\), the minimum total cost required to have \(a\) equal to \(i\) after exactly \(k\) operations. Each test case is independent.

inputFormat

The first line contains three integers \(n\), \(k\), and \(p\) (the initial index, 1-indexed). The second line contains \(n\) integers \(x_1,x_2,\dots,x_n\). Following this, there are \(n\) lines; the \(i\)-th of these contains \(k\) integers \(w_{i,1},w_{i,2},\dots,w_{i,k}\) representing the cost sequence for element \(i\).

outputFormat

Output a single line containing \(n\) space-separated integers. The \(i\)-th integer represents the minimum cost to transform \(a\) to \(i\) after exactly \(k\) operations.

sample

3 2 1
3 1 2
1 2
2 3
3 1

3 8 4