This is an answer-submission problem.

Scallions are a traditional delicacy in China. For example, in the traditional dish Peking Duck, scallions are used to enhance the aroma of the duck, making it highly acclaimed. There is even a folk saying: "A scallion a day keeps the single life away."

However, for a scallion to unleash its unique magical power, certain conditions must be met. Xiao Cong has $N$ scallions and $M$ drawers. Placing the $i$-th scallion into the $j$-th drawer generates $w_{ij}$ magical power. Naturally, Xiao Cong wants to obtain as much magical power as possible, but the drawers have volume limits, and the scallions have their own volumes. The volume of the $i$-th scallion is $a_i$, and the capacity of the $j$-th drawer is $b_j$. The sum of the volumes of the scallions in a single drawer cannot exceed that drawer's capacity, and a single scallion cannot be split between two drawers. Xiao Cong wants to know the maximum total magical power that can be generated under these conditions.

The first line contains two integers $N$ and $M$, representing the number of scallions and the number of drawers, respectively.

The next line contains $N$ integers, representing the volume of each scallion.

The next line contains $M$ integers, representing the capacity of each drawer.

The next $N$ lines each contain $M$ integers, where the $j$-th number in the $i$-th line represents the magical power generated by placing the $i$-th scallion into the $j$-th drawer.

The output should contain $N$ integers, where the $i$-th number represents the drawer index in which the $i$-th scallion is placed. If the $i$-th scallion is not placed in any drawer, output $0$.

Examples

Input 1

1 1
1
1
1

Output 1

1

Note

We have provided an executable file scorer to evaluate how much magical power your output generates. You can use the following command to evaluate your output:

./scorer input_file output_file

For each test case, there are 10 parameters $a_1, a_2, \dots, a_{10}$. If the magical power $v$ generated by your output satisfies $v \geq a_i$, we guarantee that you will receive at least $i$ points for that test case.