Little Krotka and her brother Entek are happy inhabitants of a certain $d$-dimensional world. Today, they decided to play hide-and-seek – Entek will be the first to search. Since searching in high-dimensional worlds is not the easiest task, they decided to communicate via walkie-talkies to make it easier. Additionally, each of them brought a GPS receiver.

Krotka has hidden at a certain lattice point (i.e., one where all coordinates are integers) in the Hypercubic Forest and does not intend to move until the end of the game. The forest, as the name suggests, is a hypercube with side length $r$ – it contains points with all coordinates in the interval $[0, r]$. Entek, in search of his sister, moves through the forest, occasionally reporting his location read from the GPS. We assume that Entek is always at a lattice point when reporting his location.

After reporting his location, Entek receives a "warm" or "cold" message from Krotka – Krotka informs him whether he has moved closer to her position since the previous contact.

For given $d$-dimensional points $p, x, y$, Krotka considers point $x$ to be closer to point $p$ than point $y$ if and only if: $$\max_{i=1,2,\dots,d} |x_i - p_i| < \max_{i=1,2,\dots,d} |y_i - p_i|.$$

Entek's walkie-talkie has a low-capacity battery and will allow him to make at most $k$ connections. Help him find his sister before he loses the ability to contact her.

Interaction

Krotka is hiding at a $d$-dimensional point where all coordinates are integers and belong to the interval $[0, r]$. During the game, Krotka answers truthfully and does not move.

Your program should use the provided library that simulates Krotka's responses. To use the library in a solution written in C or C++, you must include the following in your program:

#include "cielib.h"

For solutions in Java, the library will be included without the need to add extra lines to the source file.

Communication with the library is performed using the following functions:

• int podajD() – returns the dimension of the world in which Krotka and Entek live, denoted above by $d$.
• int podajK() – returns the number of possible czyCieplo queries, denoted above by $k$.
• int podajR() – returns the side length of the Hypercubic Forest, denoted above by $r$.
• int czyCieplo(int pozycja[]) – pozycja must be a $d$-element array of integers from the interval $[0, r]$, representing Entek's current position. This function always returns 0 or 1. During the program's execution, it can be called at most $k$ times. Upon the first call, the function returns 0. For each subsequent call, it returns 1 if and only if Entek's current position is closer to Krotka's position than his position at the previous call.
• void znalazlem(int pozycja[]) – pozycja must be a $d$-element array of integers from the interval $[0, r]$ representing the found position of Krotka. This function must be called exactly once, and its call will terminate your program.

In the case of C and C++, these are global functions; in the case of Java, these are static methods of the cielib class (i.e., they are called as cielib.podajD()).

Your program must not open any files or use standard input and output. The solution will be compiled together with the library using the following commands:

• C: gcc -std=c11 -static -O2 -s cielib.c cie.c -lm
• C++: g++ -std=c++11 -static -O2 -s cielib.c cie.cpp -lm
• Java: javac cie.java jar cf cie.jar *.class

In the "Files" section, you can find example library files and incorrect solutions illustrating how to use them. For the compilation commands provided above to work, the library files must be located in the current directory.

Constraints

In all tests, $2 \le r \le 10^9$, $1 \le d \le 500$, and $k \ge 100d$.

Subtasks

Your program will receive a point for a given test if, after at most $k$ calls to the czyCieplo function, it calls the znalazlem function with the correct position of Krotka. A program that uses the library incorrectly (calling functions with arguments not meeting the requirements given in the Interaction section or using standard input or output) will receive 0 points for the test.

Examples

Input 1