|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||512 MB||14||7||7||50.000%|
Joseph and Carl are playing the next funny game. There are $n$ different types of rectangular cookies, each cookie have side $X$ and $Y$ of length $x_i$ and $y_i$ respectively. Both players have access to infinite number of each cookie.
The game consists of two stages: setup and play. At the first stage, Joseph sets up the playfield.
AFter the setup stage, the play starts. The players put cookies in turns, Carl starts first. For one turn player chooses a cookie and puts it in some stack at the top. The following requirements must be held:
The player, who cannot do the correct move at his turn, lose.
You know the cookies that were chosen by Joseph. Your task is to find one of possible initial rotations of cookies which ensure that Joseph at the play stage wins when both players playing optimally, or tell that it is impossible for Joseph to win regardless of his decisions about starting cookies' orientation.
The first line of the input contains two integers $n$ and $k$ ($1 \le n, k \le 10^5$) --- number of cookie types and number of cookies used by Joseph at the setup stage.
$i$-th of the following $n$ lines contain two numbers $x_i$ and $y_i$ ($1 \le x_i, y_i \le 10^5$) --- lengths of $x$-parallel and $y$-parallel sides of the $i$-th cookie type. You may assume that no two cookie types same $x_i$ size and no two cookie types have same $y_i$ size.
The last line of the input contains $k$ integers $a_i$ ($1 \le a_i \le n$) --- cookie types used by Joseph while setting the game up.
If it is impossible for Joseph to put the chosen $k$ cookies to ensure victory, print "
impossible". Otherwise print one binary string of length $k$. The $i$-th from the left bit is equal to 0, the $i$-th cookie in order they are listed in the input is not rotated (i.e. $x_i$ is horizontal), if it is equal to 1, cookie is rotated by 90 degrees and $y_i$ is horizontal. IF there are more than one solution, you may print any of them.
5 3 1 1 4 5 3 4 5 3 6 6 1 2 4
5 3 1 1 3 4 5 3 4 5 7 7 5 1 2