Determine the Prices

Three friends, V, I, and Y, are involved in an interesting pricing puzzle. I has opened a store that sells $N$ items (numbered from $0$ to $N-1$) with an infinite supply. Each item is priced either $0$ or $1$. V knows through supernatural means that among these $N$ items, the number of items priced $1$ is exactly odd or even, as indicated by a parameter, and additionally, there is at least one item with price $1$.

V does not want to ask I directly. Instead, he employs Y to run errands. In each query, V provides two non-empty sets $S$ and $T$ (each containing distinct item indices). Y will go to the store, purchase the items in both sets, and then tell V which set has a higher total price. Formally, if (\sum_{i \in S} price_i > \sum_{i \in T} price_i) the response is 0; if (\sum_{i \in T} price_i > \sum_{i \in S} price_i) the response is 1; and if they are equal, Y returns an answer by some unknown rule. The cost of a query is defined as $|S|+|T|$. Moreover, the total cost cannot exceed a given threshold $M$ (Y’s energy limit).

Your task is to determine the price of each of the $N$ items by judiciously making queries.

You are required to implement the function find_price(task_id, N, K, ans) where:

• task_id is the subtask identifier.
• N is the number of items.
• K indicates the parity constraint: if $K=0$, then an even number of items are priced $1$; if $K=1$, then an odd number of items are priced $1$.
• ans is an array where your computed price for item $i$ should be stored in ans[i].

You can make queries via a function query(S, nS, T, nT) that takes two arrays of item indices with their sizes nS and nT, respectively, and returns (a) 0 if the sum of prices of set $S$ is greater, (b) 1 if the sum of prices of set $T$ is greater, and (c) an unknown response if the sums are equal. Note that each query has a cost of $nS+nT$.

For the purpose of this problem, you do not need to implement the interactive query functionality. Instead, design an algorithm that solves the problem under the given constraints. In our sample solution below, we provide a trivial answer that meets the parity condition.

Note: In interactive problems, you should carefully design the queries so as not to exceed the total allowed cost $M$.

inputFormat

Input consists of three integers on a single line: task_id, N, and K. task_id represents the subtask identifier, N is the number of items, and K indicates the required parity condition ($0$ for even and $1$ for odd number of items priced $1$).

outputFormat

Output a single line containing N space-separated integers, where the i-th integer is the determined price of item i (either 0 or 1).

sample

0 1 1

1