시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB32266.667%

문제

Currently, there are $n$ galactic governments in the $k$-dimensional cubic universe. The universe is a cube with two opposite vertices $(0, \ldots, 0)$ and $(C, \ldots, C)$ and sides parallel to coordinate axes. Formally, the set of points in the universe is $$U = \{(x_1, \ldots, x_k) \in \mathbb{R}^k \colon 0 \le x_i \le C\}\text{.}$$

Each galactic government claims that its territory is a parallelepiped with sides parallel to coordinate axes. The $i$-th government claims a parallelepiped with two opposite vertices $(a_{i,1}, \ldots, a_{i,k})$ and $(b_{i,1}, \ldots, b_{i,k})$ such that $a_{i,j} < b_{i,j}$ for all $j$. Formally, the $i$-th government claims the set of points $$G_i = \{(x_1, \ldots, x_k) \in U \colon a_{i,j} \le x_j \le b_{i,j}\}\text{.}$$

Note that some pieces of territory can be claimed by multiple governments.

Rick tries to find a point which is not claimed by any of the galactic governments. He has noticed that $a_{i,j}$ is an integer for all $i$ from $1$ to $n$ and all $j$ from $1$ to $k$. Rick knows that it implies that an unclaimed point exists if and only if there exists an unclaimed point $\left(\alpha_1 + \frac{1}{2}, \alpha_2 + \frac{1}{2}, \ldots, \alpha_k + \frac{1}{2}\right)$ where $\alpha_i$ are all integers. Rick likes integers, so he asks you to find $\alpha_1, \ldots, \alpha_k$ such that $\left(\alpha_1 + \frac{1}{2}, \alpha_2 + \frac{1}{2}, \ldots, \alpha_k + \frac{1}{2}\right)$ is a point in the universe and it does not belong in any of the $G_1, \ldots, G_n$. If there are multiple such points, Rick wants to find the lexicographically smallest one.

Point $\left(\beta_1 + \frac{1}{2}, \ldots, \beta_k + \frac{1}{2}\right)$ is lexicographically smaller than $\left(\gamma_1 + \frac{1}{2}, \ldots, \gamma_k + \frac{1}{2}\right)$ if there exists such $j$ ($1 \le j \le k$) such that for all $i < j$ we have $\beta_i = \gamma_i$, and $\beta_j < \gamma_j$.

입력

The first line contains three integers $n$, $k$, and $C$ ($1 \le n \le 18$, $1 \le k \le 10$, $1 \le C \le 1000$). The $i$-th of the next $n$ lines contains $2 k$ integers: $a_{i,1}, \ldots, a_{i,k}, \; b_{i,1}, \ldots, b_{i,k}$ ($0 \le a_{i,j} < b_{i,j} \le C$ for every $j$ from $1$ to $k$).

출력

Print "NO" if all points in the universe are claimed by galactic governments. Otherwise, print "YES" on the first line, and on the second line, print $k$ integers $\alpha_1, \ldots, \alpha_k$ such that $\left(\alpha_1 + \frac{1}{2}, \alpha_2 + \frac{1}{2}, \ldots, \alpha_k + \frac{1}{2}\right)$ is a point in the universe and it does not belong in any of the $G_1, \ldots, G_n$. If there are multiple solutions, print the lexicographically smallest one.

예제 입력 1

2 2 3
0 0 2 2
1 1 3 3

예제 출력 1

YES
0 2

예제 입력 2

1 3 5
0 0 0 5 5 5

예제 출력 2

NO