Curiosity Has No Limits
When Masha came to math classes today, she saw two integer sequences of length n?1n?1 on the blackboard. Let’s denote the elements of the first sequence as aiai (0≤ai≤3), and the elements of the second sequence as bibi (0≤bi≤3).
Masha became interested if or not there is an integer sequence of length nn, which elements we will denote as titi (0≤ti≤3), so that for every ii (1≤i≤n?1) the following is true:
- ai=ti|ti+1 (where | denotes the bitwise OR operation) and
- bi=ti&ti+1(where &denotes the bitwise AND operation).
The question appeared to be too difficult for Masha, so now she asked you to check whether such a sequence titi of length nn exists. If it exists, find such a sequence. If there are multiple such sequences, find any of them.
Input
The first line contains a single integer nn (2≤n≤1052≤n≤105) — the length of the sequence titi.
The second line contains n?1n?1 integers a1,a2,…,an?1a1,a2,…,an?1 (0≤ai≤3) — the first sequence on the blackboard.
The third line contains n?1n?1 integers b1,b2,…,bn?1b1,b2,…,bn?1 (0≤bi≤3) — the second sequence on the blackboard.
Output
In the first line print “YES” (without quotes), if there is a sequence titi that satisfies the conditions from the statements, and “NO” (without quotes), if there is no such sequence.
If there is such a sequence, on the second line print nn integers t1,t2,…,tnt1,t2,…,tn (0≤ti≤30≤ti≤3) — the sequence that satisfies the statements conditions.
If there are multiple answers, print any of them.
Examples
input
4
3 3 2
1 2 0
output
YES
1 3 2 0
input
3
1 3
3 2
output
NO
Note
In the first example it’s easy to see that the sequence from output satisfies the given conditions:
- t1|t2=(01)|(11)=(11)=3=a1 and t1&t2=(01)&(11)=(01)=1=b1;
- t2|t3=(11)|(10)=(11)=3=a2 and t2&t3=(11)&(10)=(10)=2=b2;
- t3|t4=(10)|(00)=(10)=2=a3 and t3&t4=(10)&(00)=(00)=0=b3.
In the second example there is no such sequence.
题意：
给你a[],b[]，让你求出t[]. a[i]= t[i] | t[i+1]， b[i] = t[i] & t[i+1].满足这两条规则，且t[i]的范围只能说0，1，2。如果有解，输出"YES", 并输出t[i]。
题目链接：
http://codeforces.com/contest/1072/problem/B
思路：
dfs，先他给第一位的值，然后开始一位一位开始搜索， 当当前位满足条件时，搜索下一位，搜索到最后输出即可。
代码：
``
#include<bits/stdc++.h>
using namespace std;
int a[200000], b[200000];
int t;
int p[200000];
void dfs(int step, int k)
{
if(step == t) {
cout << "YES" << endl;for(int i = 1; i <= t; i++)cout << p[i] << " "; cout << endl;exit(0);}for(int i = 0; i <= 3; i++) {
if(((k | i) == a[step]) && ((k & i) == b[step])) {
p[step+1] = i;dfs(step+1, i);}}}
int main()
{
cin >> t;for(int i = 1; i < t; i++) cin >> a[i];for(int i = 1; i < t; i++) cin >> b[i];for(int i = 0; i <= 3; i++) {
p[1] = i;dfs(1, i);} cout << "NO" << endl;return 0;
}
``