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 <algorithm>
#include <vector>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int n;
int cnt[6];
int tikan[6][3] = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};

int main() {
	int i, j;
	
	cin >> n;
	rep(i, n) {
		int w, a;
		int num[3] = {0, 1, 2};
		cin >> w;
		rep(j, w) {
			cin >> a;
			swap(num[a], num[a + 1]);
		}
		int pos[3];
		rep(j, 3) { pos[num[j]] = j; }
		
		int type;
		if (pos[0] == 0 && pos[1] == 1 && pos[2] == 2) type = 0;
		if (pos[0] == 0 && pos[1] == 2 && pos[2] == 1) type = 1;
		if (pos[0] == 1 && pos[1] == 0 && pos[2] == 2) type = 2;
		if (pos[0] == 1 && pos[1] == 2 && pos[2] == 0) type = 3;
		if (pos[0] == 2 && pos[1] == 0 && pos[2] == 1) type = 4;
		if (pos[0] == 2 && pos[1] == 1 && pos[2] == 0) type = 5;
		cnt[type]++;
	}
	
	if (cnt[0] >= 1) { cout << "yes" << endl; return 0; }
	if (cnt[1] >= 2 || cnt[5] >= 2 || cnt[2] >= 2) { cout << "yes" << endl; return 0; }
	if (cnt[3] >= 1 && cnt[4] >= 1) { cout << "yes" << endl; return 0; }
	if (cnt[3] >= 3 || cnt[4] >= 3) { cout << "yes" << endl; return 0; }
	
	//高々5個になったので全探索できる
	vector<int> types;
	rep(i, 6) {
		rep(j, cnt[i]) { types.push_back(i); }
	}
	
	vector<int> perm;
	rep(i, types.size()) perm.push_back(i);
	
	do {
		int pos[3] = {0, 1, 2};
		rep(i, types.size()) {
			int type = types[perm[i]];
			rep(j, 3) {
				pos[j] = tikan[type][pos[j]];
			}
		}
		
		if (pos[0] == 0 && pos[1] == 1 && pos[2] == 2) {
			cout << "yes" << endl;
			return 0;
		}
	} while (next_permutation(perm.begin(), perm.end()));
	
	cout << "no" << endl;
	return 0;
}