1031B.md (2553B)
1 Source: https://codeforces.com/problemset/problem/1031/B 2 3 B. Curiosity Has No Limits 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 When Masha came to math classes today, she saw two integer sequences of length $n - 1$ on the blackboard. Let's denote the elements of the first sequence as $a_i$ ($0 \le a_i \le 3$), and the elements of the second sequence as $b_i$ ($0 \le b_i \le 3$). 22 23 Masha became interested if or not there is an integer sequence of length $n$, which elements we will denote as $t_i$ ($0 \le t_i \le 3$), so that for every $i$ ($1 \le i \le n - 1$) the following is true: 24 25 * $a_i = t_i | t_{i + 1}$ (where $|$ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR)) and 26 * $b_i = t_i \& t_{i + 1}$ (where $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND)). 27 28 The question appeared to be too difficult for Masha, so now she asked you to check whether such a sequence $t_i$ of length $n$ exists. If it exists, find such a sequence. If there are multiple such sequences, find any of them. 29 30 Input 31 32 The first line contains a single integer $n$ ($2 \le n \le 10^5$) — the length of the sequence $t_i$. 33 34 The second line contains $n - 1$ integers $a_1, a_2, \ldots, a_{n-1}$ ($0 \le a_i \le 3$) — the first sequence on the blackboard. 35 36 The third line contains $n - 1$ integers $b_1, b_2, \ldots, b_{n-1}$ ($0 \le b_i \le 3$) — the second sequence on the blackboard. 37 38 Output 39 40 In the first line print "YES" (without quotes), if there is a sequence $t_i$ that satisfies the conditions from the statements, and "NO" (without quotes), if there is no such sequence. 41 42 If there is such a sequence, on the second line print $n$ integers $t_1, t_2, \ldots, t_n$ ($0 \le t_i \le 3$) — the sequence that satisfies the statements conditions. 43 44 If there are multiple answers, print any of them. 45 46 Examples 47 48 Input 49 50 ``` 51 4 52 3 3 2 53 1 2 0 54 ``` 55 56 Output 57 58 ``` 59 YES 60 1 3 2 0 61 ``` 62 63 Input 64 65 ``` 66 3 67 1 3 68 3 2 69 ``` 70 71 Output 72 73 ``` 74 NO 75 ``` 76 77 Note 78 79 In the first example it's easy to see that the sequence from output satisfies the given conditions: 80 81 * $t_1 | t_2 = (01_2) | (11_2) = (11_2) = 3 = a_1$ and $t_1 \& t_2 = (01_2) \& (11_2) = (01_2) = 1 = b_1$; 82 * $t_2 | t_3 = (11_2) | (10_2) = (11_2) = 3 = a_2$ and $t_2 \& t_3 = (11_2) \& (10_2) = (10_2) = 2 = b_2$; 83 * $t_3 | t_4 = (10_2) | (00_2) = (10_2) = 2 = a_3$ and $t_3 \& t_4 = (10_2) \& (00_2) = (00_2) = 0 = b_3$. 84 85 In the second example there is no such sequence.