Problem: Problem

There are $ N $ Amidakuji with 3 vertical lines.
No matter which line you start from, the Amidakuji that ends at the starting line is considered a good Amidakuji.
You can select one or more Amidakuji and connect them vertically in any order.
Output "yes" if you can make a good Amidakuji, otherwise output "no".

There are $ w_i $ horizontal lines in the $ i $ th Amidakuji.
$ a_ {i, j} $ indicates whether the $ j $ th horizontal bar from the top of Amidakuji $ i $ extends from the central vertical line to the left or right.
If $ a_ {i, j} $ is 0, it means that it extends to the left, and if it is 1, it means that it extends to the right.

Constraints

The input satisfies the following conditions.

* $ 1 \ le N \ le 50 $
* $ 0 \ le w_i \ le 100 $
* $ a_ {i, j} $ is 0 or 1

Input

The input is given in the following format.


$ N $
$ w_1 $ $ a_ {1,1} $ $ a_ {1,2} $ ... $ a_ {1, w_1} $
$ w_2 $ $ a_ {2,1} $ $ a_ {2,2} $ ... $ a_ {2, w_2} $
...
$ w_N $ $ a_ {N, 1} $ $ a_ {N, 2} $ ... $ a_ {N, w_N} $


All inputs are given as integers.
$ N $ is given on the first line.
$ W_i $ and $ w_i $ $ a_ {i, j} $ are given on the following $ N $ line, separated by blanks.

Output

If you can make a good Amidakuji, it outputs "yes", otherwise it outputs "no".

Examples

Input

3
2 0 0
1 1
5 1 0 0 1 0


Output

yes


Input

2
1 1
1 0


Output

no

Solution (in CPP):

Solution:
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
 
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define C(i) cin>>i
#define C2(i,j) cin>>i>>j
#define C3(i,j,k) cin>>i>>j>>k
#define C4(i,j,k,m) cin>>i>>j>>k>>m
////////////////////////////////////////////////////////////

struct p{
	int f;
	int s;
	int t;
};

int dore( int p , vector<int> &a ){
	rep(i,0,a.size()){
		if( a[i] == 0 ){
			if( p == 0 ) p = 1;
			else if( p == 1 ) p = 0;
			else continue;
		}
		else if( a[i] == 1 ){
			if( p == 1 ) p = 2;
			else if( p == 2 ) p = 1;
			else continue;
		}
	}

	ret p;
}

int main(){
	int n;
	cin >> n;
	
	vector<int> mp(6);

	rep(i,0,n){
		int w;
		cin >> w;
		vector<int> a(w);
		rep(j,0,w) cin >> a[j];
		
		int g0 = dore(0,a);
		int g1 = dore(1,a);

		if( g0 == 0 && g1 == 1 )
			mp[0]++;
		else if( g0 == 1 && g1 == 0)
			mp[1]++;
		else if( g0 == 0 && g1 == 2)
			mp[2]++;
		else if( g0 == 1 && g1 == 2)
			mp[3]++;
		else if( g0 == 2 && g1 == 0)
			mp[4]++;
		else if( g0 == 2 && g1 == 1)
			mp[5]++;
	}

	if( mp[0] > 0 || mp[1] > 1 || mp[2] > 1 || mp[3] > 2 || mp[4] > 2 || mp[5] > 1 ){
		yes;
		ret 0;
	}
	
	vector<int> v;
	rep(i,1,6){
		rep(j,0,mp[i])
			v.push_back(i);
	}
	
	vsort(v);
	do{
		vector<int> ami={0,1,2};
		rep(i,0,v.size()){
			switch(v[i]){
				case 1:
					swap(ami[0],ami[1]);
					break;
				case 2:
					swap(ami[1],ami[2]);
					break;
				case 3:{
					vector<int> tmp{ami[2],ami[0],ami[1]};
					ami = tmp;
					break;}
				case 4:{
					vector<int> tmp{ami[1],ami[2],ami[0]};
					ami = tmp;
					break;}
				case 5:
					swap(ami[0],ami[2]);
					break;
				default:
					break;
			}
		}
		if(ami[0] == 0 && ami[1] == 1 ){
			yes;
			ret 0;
		}
		
	}while(next_permutation(v.begin(),v.end()));
	
	no;
	ret 0;
}