QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#69057#5247. Walizki [C]wiktorlewicki8 334ms3588kbC++2310.1kb2022-12-23 01:47:142022-12-23 01:47:15

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-23 01:47:15]
  • 评测
  • 测评结果:8
  • 用时:334ms
  • 内存:3588kb
  • [2022-12-23 01:47:14]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 1e2 + 14, lg = 15;
typedef long long ll;
/*
  ######################################################################
  #######################   THE   BIG   INT   ##########################
*/
const int base = 1000000000;
const int base_digits = 9; 
struct bigint {
	vector<int> a;
	int sign;
	/*<arpa>*/
	int size(){
		if(a.empty())return 0;
		int ans=(a.size()-1)*base_digits;
		int ca=a.back();
		while(ca)
			ans++,ca/=10;
		return ans;
	}
	bigint operator ^(const bigint &v){
		bigint ans=1,a=*this,b=v;
		while(!b.isZero()){
			if(b%2)
				ans*=a;
			a*=a,b/=2;
		}
		return ans;
	}
	string to_string(){
		stringstream ss;
		ss << *this;
		string s;
		ss >> s;
		return s;
	}
	int sumof(){
		string s = to_string();
		int ans = 0;
		for(auto c : s)  ans += c - '0';
		return ans;
	}
	/*</arpa>*/
	bigint() :
		sign(1) {
	}
 
	bigint(long long v) {
		*this = v;
	}
 
	bigint(const string &s) {
		read(s);
	}
 
	void operator=(const bigint &v) {
		sign = v.sign;
		a = v.a;
	}
 
	void operator=(long long v) {
		sign = 1;
		a.clear();
		if (v < 0)
			sign = -1, v = -v;
		for (; v > 0; v = v / base)
			a.push_back(v % base);
	}
 
	bigint operator+(const bigint &v) const {
		if (sign == v.sign) {
			bigint res = v;
 
			for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
				if (i == (int) res.a.size())
					res.a.push_back(0);
				res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
				carry = res.a[i] >= base;
				if (carry)
					res.a[i] -= base;
			}
			return res;
		}
		return *this - (-v);
	}
 
	bigint operator-(const bigint &v) const {
		if (sign == v.sign) {
			if (abs() >= v.abs()) {
				bigint res = *this;
				for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
					res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
					carry = res.a[i] < 0;
					if (carry)
						res.a[i] += base;
				}
				res.trim();
				return res;
			}
			return -(v - *this);
		}
		return *this + (-v);
	}
 
	void operator*=(int v) {
		if (v < 0)
			sign = -sign, v = -v;
		for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
			if (i == (int) a.size())
				a.push_back(0);
			long long cur = a[i] * (long long) v + carry;
			carry = (int) (cur / base);
			a[i] = (int) (cur % base);
			//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
		}
		trim();
	}
 
	bigint operator*(int v) const {
		bigint res = *this;
		res *= v;
		return res;
	}
 
	void operator*=(long long v) {
		if (v < 0)
			sign = -sign, v = -v;
		if(v > base){
			*this = *this * (v / base) * base + *this * (v % base);
			return ;
		}
		for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
			if (i == (int) a.size())
				a.push_back(0);
			long long cur = a[i] * (long long) v + carry;
			carry = (int) (cur / base);
			a[i] = (int) (cur % base);
			//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
		}
		trim();
	}
 
	bigint operator*(long long v) const {
		bigint res = *this;
		res *= v;
		return res;
	}
 
	friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
		int norm = base / (b1.a.back() + 1);
		bigint a = a1.abs() * norm;
		bigint b = b1.abs() * norm;
		bigint q, r;
		q.a.resize(a.a.size());
 
		for (int i = a.a.size() - 1; i >= 0; i--) {
			r *= base;
			r += a.a[i];
			int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
			int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
			int d = ((long long) base * s1 + s2) / b.a.back();
			r -= b * d;
			while (r < 0)
				r += b, --d;
			q.a[i] = d;
		}
 
		q.sign = a1.sign * b1.sign;
		r.sign = a1.sign;
		q.trim();
		r.trim();
		return make_pair(q, r / norm);
	}
 
	bigint operator/(const bigint &v) const {
		return divmod(*this, v).first;
	}
 
	bigint operator%(const bigint &v) const {
		return divmod(*this, v).second;
	}
 
	void operator/=(int v) {
		if (v < 0)
			sign = -sign, v = -v;
		for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
			long long cur = a[i] + rem * (long long) base;
			a[i] = (int) (cur / v);
			rem = (int) (cur % v);
		}
		trim();
	}
 
	bigint operator/(int v) const {
		bigint res = *this;
		res /= v;
		return res;
	}
 
	int operator%(int v) const {
		if (v < 0)
			v = -v;
		int m = 0;
		for (int i = a.size() - 1; i >= 0; --i)
			m = (a[i] + m * (long long) base) % v;
		return m * sign;
	}
 
	void operator+=(const bigint &v) {
		*this = *this + v;
	}
	void operator-=(const bigint &v) {
		*this = *this - v;
	}
	void operator*=(const bigint &v) {
		*this = *this * v;
	}
	void operator/=(const bigint &v) {
		*this = *this / v;
	}
 
	bool operator<(const bigint &v) const {
		if (sign != v.sign)
			return sign < v.sign;
		if (a.size() != v.a.size())
			return a.size() * sign < v.a.size() * v.sign;
		for (int i = a.size() - 1; i >= 0; i--)
			if (a[i] != v.a[i])
				return a[i] * sign < v.a[i] * sign;
		return false;
	}
 
	bool operator>(const bigint &v) const {
		return v < *this;
	}
	bool operator<=(const bigint &v) const {
		return !(v < *this);
	}
	bool operator>=(const bigint &v) const {
		return !(*this < v);
	}
	bool operator==(const bigint &v) const {
		return !(*this < v) && !(v < *this);
	}
	bool operator!=(const bigint &v) const {
		return *this < v || v < *this;
	}
 
	void trim() {
		while (!a.empty() && !a.back())
			a.pop_back();
		if (a.empty())
			sign = 1;
	}
 
	bool isZero() const {
		return a.empty() || (a.size() == 1 && !a[0]);
	}
 
	bigint operator-() const {
		bigint res = *this;
		res.sign = -sign;
		return res;
	}
 
	bigint abs() const {
		bigint res = *this;
		res.sign *= res.sign;
		return res;
	}
 
	long long longValue() const {
		long long res = 0;
		for (int i = a.size() - 1; i >= 0; i--)
			res = res * base + a[i];
		return res * sign;
	}
 
	friend bigint gcd(const bigint &a, const bigint &b) {
		return b.isZero() ? a : gcd(b, a % b);
	}
	friend bigint lcm(const bigint &a, const bigint &b) {
		return a / gcd(a, b) * b;
	}
 
	void read(const string &s) {
		sign = 1;
		a.clear();
		int pos = 0;
		while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
			if (s[pos] == '-')
				sign = -sign;
			++pos;
		}
		for (int i = s.size() - 1; i >= pos; i -= base_digits) {
			int x = 0;
			for (int j = max(pos, i - base_digits + 1); j <= i; j++)
				x = x * 10 + s[j] - '0';
			a.push_back(x);
		}
		trim();
	}
 
	friend istream& operator>>(istream &stream, bigint &v) {
		string s;
		stream >> s;
		v.read(s);
		return stream;
	}
 
	friend ostream& operator<<(ostream &stream, const bigint &v) {
		if (v.sign == -1)
			stream << '-';
		stream << (v.a.empty() ? 0 : v.a.back());
		for (int i = (int) v.a.size() - 2; i >= 0; --i)
			stream << setw(base_digits) << setfill('0') << v.a[i];
		return stream;
	}
 
	static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
		vector<long long> p(max(old_digits, new_digits) + 1);
		p[0] = 1;
		for (int i = 1; i < (int) p.size(); i++)
			p[i] = p[i - 1] * 10;
		vector<int> res;
		long long cur = 0;
		int cur_digits = 0;
		for (int i = 0; i < (int) a.size(); i++) {
			cur += a[i] * p[cur_digits];
			cur_digits += old_digits;
			while (cur_digits >= new_digits) {
				res.push_back(int(cur % p[new_digits]));
				cur /= p[new_digits];
				cur_digits -= new_digits;
			}
		}
		res.push_back((int) cur);
		while (!res.empty() && !res.back())
			res.pop_back();
		return res;
	}
 
	typedef vector<long long> vll;
 
	static vll karatsubaMultiply(const vll &a, const vll &b) {
		int n = a.size();
		vll res(n + n);
		if (n <= 32) {
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					res[i + j] += a[i] * b[j];
			return res;
		}
 
		int k = n >> 1;
		vll a1(a.begin(), a.begin() + k);
		vll a2(a.begin() + k, a.end());
		vll b1(b.begin(), b.begin() + k);
		vll b2(b.begin() + k, b.end());
 
		vll a1b1 = karatsubaMultiply(a1, b1);
		vll a2b2 = karatsubaMultiply(a2, b2);
 
		for (int i = 0; i < k; i++)
			a2[i] += a1[i];
		for (int i = 0; i < k; i++)
			b2[i] += b1[i];
 
		vll r = karatsubaMultiply(a2, b2);
		for (int i = 0; i < (int) a1b1.size(); i++)
			r[i] -= a1b1[i];
		for (int i = 0; i < (int) a2b2.size(); i++)
			r[i] -= a2b2[i];
 
		for (int i = 0; i < (int) r.size(); i++)
			res[i + k] += r[i];
		for (int i = 0; i < (int) a1b1.size(); i++)
			res[i] += a1b1[i];
		for (int i = 0; i < (int) a2b2.size(); i++)
			res[i + n] += a2b2[i];
		return res;
	}
 
	bigint operator*(const bigint &v) const {
		vector<int> a6 = convert_base(this->a, base_digits, 6);
		vector<int> b6 = convert_base(v.a, base_digits, 6);
		vll a(a6.begin(), a6.end());
		vll b(b6.begin(), b6.end());
		while (a.size() < b.size())
			a.push_back(0);
		while (b.size() < a.size())
			b.push_back(0);
		while (a.size() & (a.size() - 1))
			a.push_back(0), b.push_back(0);
		vll c = karatsubaMultiply(a, b);
		bigint res;
		res.sign = sign * v.sign;
		for (int i = 0, carry = 0; i < (int) c.size(); i++) {
			long long cur = c[i] + carry;
			res.a.push_back((int) (cur % 1000000));
			carry = (int) (cur / 1000000);
		}
		res.a = convert_base(res.a, 6, base_digits);
		res.trim();
		return res;
	}
};
/*
  #######################   THE   BIG   INT   ##########################
  ######################################################################
*/
const int N = 1e2 + 5;
vector<int> kraw[N];
ll n;
bigint dp[N], k[N];
bigint NWW(bigint a, bigint b){
	bigint res = a*b/__gcd(a, b);
	return res;
}
void dfs(){
	for(int i=2;i<=n;i++) dp[i]=0;
	for(int i=1;i<=n;i++){
		if(k[i]!=0&&dp[i]%k[i]!=0){
			bigint pom = NWW(dp[i], k[i]);
			pom/=dp[i];
			dp[1]*=pom;
			dfs();
			return;
		}
		for(auto v : kraw[i]){
			dp[v]+=(dp[i]/k[i]);
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		long long x;
		cin>>x;
		k[i]=x;
		for(int j=1;j<=x;j++){
			long long a;
			cin>>a;
			kraw[i].pb(a);
		}
	}
	dp[1]=1;
	dfs();
	cout<<dp[1];
	return 0;
}

詳細信息

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 2ms
memory: 3348kb

input:

1
0

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3472kb

input:

3
2 2 3
1 3
0

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3352kb

input:

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

output:

12

result:

ok single line: '12'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3472kb

input:

7
6 2 3 4 5 6 7
5 3 4 5 6 7
4 4 5 6 7
3 5 6 7
2 6 7
1 7
0

output:

60

result:

ok single line: '60'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3504kb

input:

9
8 2 3 4 5 6 7 8 9
7 3 4 5 6 7 8 9
6 4 5 6 7 8 9
5 5 6 7 8 9
4 6 7 8 9
3 7 8 9
2 8 9
1 9
0

output:

840

result:

ok single line: '840'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3368kb

input:

10
0
6 3 5 6 8 9 10
4 4 6 7 8
3 6 7 8
4 6 7 8 9
2 9 10
0
1 9
1 10
0

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3324kb

input:

10
5 3 5 7 8 10
2 9 10
3 5 6 10
3 6 8 9
1 7
1 8
2 8 9
0
0
0

output:

30

result:

ok single line: '30'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3504kb

input:

10
8 2 3 4 6 7 8 9 10
7 3 4 5 6 7 9 10
7 4 5 6 7 8 9 10
5 6 7 8 9 10
4 6 7 8 9
4 7 8 9 10
2 8 9
2 9 10
0
0

output:

125440

result:

ok single line: '125440'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3540kb

input:

10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
0

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3416kb

input:

10
3 2 3 4
3 3 4 5
3 4 5 6
3 5 6 7
3 6 7 8
3 7 8 9
3 8 9 10
2 9 10
1 10
0

output:

2187

result:

ok single line: '2187'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3420kb

input:

10
5 2 7 8 9 10
5 3 7 8 9 10
5 4 7 8 9 10
5 5 7 8 9 10
5 6 7 8 9 10
4 7 8 9 10
3 8 9 10
2 9 10
1 10
0

output:

37500

result:

ok single line: '37500'

Subtask #2:

score: 1
Accepted

Test #12:

score: 1
Accepted
time: 2ms
memory: 3500kb

input:

2
1 2
0

output:

1

result:

ok single line: '1'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3440kb

input:

4
3 2 3 4
2 3 4
1 4
0

output:

6

result:

ok single line: '6'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3464kb

input:

6
5 2 3 4 5 6
4 3 4 5 6
3 4 5 6
2 5 6
1 6
0

output:

60

result:

ok single line: '60'

Test #15:

score: 0
Accepted
time: 2ms
memory: 3352kb

input:

8
7 2 3 4 5 6 7 8
6 3 4 5 6 7 8
5 4 5 6 7 8
4 5 6 7 8
3 6 7 8
2 7 8
1 8
0

output:

420

result:

ok single line: '420'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3468kb

input:

10
9 2 3 4 5 6 7 8 9 10
8 3 4 5 6 7 8 9 10
7 4 5 6 7 8 9 10
6 5 6 7 8 9 10
5 6 7 8 9 10
4 7 8 9 10
3 8 9 10
2 9 10
1 10
0

output:

2520

result:

ok single line: '2520'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3328kb

input:

10
6 2 3 6 8 9 10
4 3 5 6 10
3 6 7 10
2 7 8
1 10
4 7 8 9 10
0
1 9
1 10
0

output:

72

result:

ok single line: '72'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3324kb

input:

10
5 2 6 7 8 10
4 4 5 6 8
1 5
3 5 8 10
3 7 8 10
3 7 9 10
1 8
2 9 10
0
0

output:

360

result:

ok single line: '360'

Test #19:

score: 0
Accepted
time: 2ms
memory: 3544kb

input:

9
8 2 3 4 5 6 7 8 9
6 3 4 5 6 8 9
6 4 5 6 7 8 9
4 5 7 8 9
3 6 7 9
3 7 8 9
2 8 9
1 9
0

output:

20736

result:

ok single line: '20736'

Test #20:

score: 0
Accepted
time: 2ms
memory: 3324kb

input:

10
2 2 3
2 3 4
2 4 5
2 5 6
2 6 7
2 7 8
2 8 9
2 9 10
1 10
0

output:

256

result:

ok single line: '256'

Test #21:

score: 0
Accepted
time: 2ms
memory: 3324kb

input:

10
4 2 3 4 5
4 3 4 5 6
4 4 5 6 7
4 5 6 7 8
4 6 7 8 9
4 7 8 9 10
3 8 9 10
2 9 10
1 10
0

output:

12288

result:

ok single line: '12288'

Test #22:

score: 0
Accepted
time: 1ms
memory: 3320kb

input:

10
0
0
0
0
0
0
0
0
0
0

output:

1

result:

ok single line: '1'

Subtask #3:

score: 1
Accepted

Test #23:

score: 1
Accepted
time: 2ms
memory: 3508kb

input:

11
10 2 3 4 5 6 7 8 9 10 11
9 3 4 5 6 7 8 9 10 11
8 4 5 6 7 8 9 10 11
7 5 6 7 8 9 10 11
6 6 7 8 9 10 11
5 7 8 9 10 11
4 8 9 10 11
3 9 10 11
2 10 11
1 11
0

output:

2520

result:

ok single line: '2520'

Test #24:

score: 0
Accepted
time: 1ms
memory: 3368kb

input:

13
12 2 3 4 5 6 7 8 9 10 11 12 13
11 3 4 5 6 7 8 9 10 11 12 13
10 4 5 6 7 8 9 10 11 12 13
9 5 6 7 8 9 10 11 12 13
8 6 7 8 9 10 11 12 13
7 7 8 9 10 11 12 13
6 8 9 10 11 12 13
5 9 10 11 12 13
4 10 11 12 13
3 11 12 13
2 12 13
1 13
0

output:

27720

result:

ok single line: '27720'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3460kb

input:

15
14 2 3 4 5 6 7 8 9 10 11 12 13 14 15
13 3 4 5 6 7 8 9 10 11 12 13 14 15
12 4 5 6 7 8 9 10 11 12 13 14 15
11 5 6 7 8 9 10 11 12 13 14 15
10 6 7 8 9 10 11 12 13 14 15
9 7 8 9 10 11 12 13 14 15
8 8 9 10 11 12 13 14 15
7 9 10 11 12 13 14 15
6 10 11 12 13 14 15
5 11 12 13 14 15
4 12 13 14 15
3 13 14 1...

output:

360360

result:

ok single line: '360360'

Test #26:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

17
16 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
15 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
14 4 5 6 7 8 9 10 11 12 13 14 15 16 17
13 5 6 7 8 9 10 11 12 13 14 15 16 17
12 6 7 8 9 10 11 12 13 14 15 16 17
11 7 8 9 10 11 12 13 14 15 16 17
10 8 9 10 11 12 13 14 15 16 17
9 9 10 11 12 13 14 15 16 17
8 10 11 12...

output:

720720

result:

ok single line: '720720'

Test #27:

score: 0
Accepted
time: 2ms
memory: 3464kb

input:

19
18 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
17 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
16 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
15 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
14 6 7 8 9 10 11 12 13 14 15 16 17 18 19
13 7 8 9 10 11 12 13 14 15 16 17 18 19
12 8 9 10 11 12 13 14 15 16 17 18...

output:

12252240

result:

ok single line: '12252240'

Test #28:

score: 0
Accepted
time: 2ms
memory: 3416kb

input:

20
1 20
12 3 4 5 6 7 10 11 13 14 15 16 18
7 5 8 9 11 12 13 18
12 5 7 8 10 11 12 13 14 16 17 18 19
7 8 12 13 15 18 19 20
9 7 8 9 10 11 14 15 16 18
6 8 9 13 17 18 20
10 9 10 11 13 14 15 16 18 19 20
6 11 12 15 16 18 19
4 11 14 18 19
5 15 16 17 18 19
4 13 14 16 17
5 14 15 16 18 19
6 15 16 17 18 19 20
2 ...

output:

1

result:

ok single line: '1'

Test #29:

score: 0
Accepted
time: 2ms
memory: 3460kb

input:

20
11 3 5 6 7 9 11 12 13 15 18 20
10 3 4 5 6 7 10 12 13 19 20
13 4 5 6 8 9 10 12 13 14 15 17 18 19
7 5 7 9 10 12 15 20
6 7 8 13 17 18 19
7 11 12 13 15 16 18 20
4 10 13 14 19
8 10 11 13 14 15 16 19 20
7 11 12 13 16 18 19 20
5 13 15 16 18 19
4 14 16 17 20
3 15 19 20
1 16
1 18
2 16 20
2 17 19
1 20
0
1 ...

output:

13453440

result:

ok single line: '13453440'

Test #30:

score: 0
Accepted
time: 4ms
memory: 3420kb

input:

20
19 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
18 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
16 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20
15 5 6 7 8 10 11 12 13 14 15 16 17 18 19 20
13 6 7 9 10 11 12 13 15 16 17 18 19 20
13 7 8 9 10 11 12 14 15 16 17 18 19 20
13 8 9 10 11 12 13 14 15 16 ...

output:

30792244234752000

result:

ok single line: '30792244234752000'

Test #31:

score: 0
Accepted
time: 2ms
memory: 3432kb

input:

20
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
0

output:

1

result:

ok single line: '1'

Test #32:

score: 0
Accepted
time: 3ms
memory: 3372kb

input:

20
3 2 3 4
3 3 4 5
3 4 5 6
3 5 6 7
3 6 7 8
3 7 8 9
3 8 9 10
3 9 10 11
3 10 11 12
3 11 12 13
3 12 13 14
3 13 14 15
3 14 15 16
3 15 16 17
3 16 17 18
3 17 18 19
3 18 19 20
2 19 20
1 20
0

output:

258280326

result:

ok single line: '258280326'

Test #33:

score: 0
Accepted
time: 3ms
memory: 3508kb

input:

20
10 2 12 13 14 15 16 17 18 19 20
10 3 12 13 14 15 16 17 18 19 20
10 4 12 13 14 15 16 17 18 19 20
10 5 12 13 14 15 16 17 18 19 20
10 6 12 13 14 15 16 17 18 19 20
10 7 12 13 14 15 16 17 18 19 20
10 8 12 13 14 15 16 17 18 19 20
10 9 12 13 14 15 16 17 18 19 20
10 10 12 13 14 15 16 17 18 19 20
10 11 12...

output:

630000000000

result:

ok single line: '630000000000'

Subtask #4:

score: 1
Accepted

Test #34:

score: 1
Accepted
time: 0ms
memory: 3464kb

input:

12
11 2 3 4 5 6 7 8 9 10 11 12
10 3 4 5 6 7 8 9 10 11 12
9 4 5 6 7 8 9 10 11 12
8 5 6 7 8 9 10 11 12
7 6 7 8 9 10 11 12
6 7 8 9 10 11 12
5 8 9 10 11 12
4 9 10 11 12
3 10 11 12
2 11 12
1 12
0

output:

27720

result:

ok single line: '27720'

Test #35:

score: 0
Accepted
time: 2ms
memory: 3420kb

input:

14
13 2 3 4 5 6 7 8 9 10 11 12 13 14
12 3 4 5 6 7 8 9 10 11 12 13 14
11 4 5 6 7 8 9 10 11 12 13 14
10 5 6 7 8 9 10 11 12 13 14
9 6 7 8 9 10 11 12 13 14
8 7 8 9 10 11 12 13 14
7 8 9 10 11 12 13 14
6 9 10 11 12 13 14
5 10 11 12 13 14
4 11 12 13 14
3 12 13 14
2 13 14
1 14
0

output:

360360

result:

ok single line: '360360'

Test #36:

score: 0
Accepted
time: 2ms
memory: 3476kb

input:

16
15 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
14 3 4 5 6 7 8 9 10 11 12 13 14 15 16
13 4 5 6 7 8 9 10 11 12 13 14 15 16
12 5 6 7 8 9 10 11 12 13 14 15 16
11 6 7 8 9 10 11 12 13 14 15 16
10 7 8 9 10 11 12 13 14 15 16
9 8 9 10 11 12 13 14 15 16
8 9 10 11 12 13 14 15 16
7 10 11 12 13 14 15 16
6 11 12 13 1...

output:

360360

result:

ok single line: '360360'

Test #37:

score: 0
Accepted
time: 2ms
memory: 3416kb

input:

18
17 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
16 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
15 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
14 5 6 7 8 9 10 11 12 13 14 15 16 17 18
13 6 7 8 9 10 11 12 13 14 15 16 17 18
12 7 8 9 10 11 12 13 14 15 16 17 18
11 8 9 10 11 12 13 14 15 16 17 18
10 9 10 11 12 13 ...

output:

12252240

result:

ok single line: '12252240'

Test #38:

score: 0
Accepted
time: 3ms
memory: 3328kb

input:

20
19 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
18 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
17 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
16 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
15 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
14 7 8 9 10 11 12 13 14 15 16 17 18 19 20
13 8 9 10 11 12...

output:

232792560

result:

ok single line: '232792560'

Test #39:

score: 0
Accepted
time: 3ms
memory: 3436kb

input:

20
7 3 7 8 14 15 19 20
12 3 5 6 8 9 10 13 14 16 17 18 20
10 4 6 7 10 12 13 14 17 18 20
7 6 9 11 12 13 18 20
5 7 14 17 18 19
5 9 13 17 18 20
5 8 9 15 16 18
6 9 11 12 13 14 19
3 10 16 18
8 12 13 14 16 17 18 19 20
9 12 13 14 15 16 17 18 19 20
3 13 17 18
3 16 17 20
3 15 17 20
3 16 17 18
2 17 19
3 18 19 ...

output:

9525600

result:

ok single line: '9525600'

Test #40:

score: 0
Accepted
time: 1ms
memory: 3468kb

input:

20
12 2 4 5 6 7 11 12 15 17 18 19 20
10 3 6 7 8 11 12 14 16 19 20
7 4 5 8 9 11 16 19
5 9 11 13 14 20
9 6 8 12 13 14 16 17 18 19
10 7 8 9 11 12 15 16 18 19 20
6 12 13 15 17 18 20
8 9 11 13 14 16 18 19 20
5 10 13 18 19 20
4 12 14 17 19
4 13 15 17 20
5 15 17 18 19 20
2 16 18
3 15 19 20
1 16
2 19 20
2 1...

output:

72576000

result:

ok single line: '72576000'

Test #41:

score: 0
Accepted
time: 1ms
memory: 3440kb

input:

19
18 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
16 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
15 4 5 6 7 8 9 10 11 12 13 14 15 17 18 19
15 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
12 6 7 8 9 10 11 12 13 15 16 18 19
12 7 8 9 10 11 12 13 14 16 17 18 19
12 8 9 10 11 12 13 14 15 16 17 18 19
10 9 10 11...

output:

1625330810880000

result:

ok single line: '1625330810880000'

Test #42:

score: 0
Accepted
time: 2ms
memory: 3396kb

input:

20
2 2 3
2 3 4
2 4 5
2 5 6
2 6 7
2 7 8
2 8 9
2 9 10
2 10 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 16
2 16 17
2 17 18
2 18 19
2 19 20
1 20
0

output:

262144

result:

ok single line: '262144'

Test #43:

score: 0
Accepted
time: 3ms
memory: 3404kb

input:

20
4 2 3 4 5
4 3 4 5 6
4 4 5 6 7
4 5 6 7 8
4 6 7 8 9
4 7 8 9 10
4 8 9 10 11
4 9 10 11 12
4 10 11 12 13
4 11 12 13 14
4 12 13 14 15
4 13 14 15 16
4 14 15 16 17
4 15 16 17 18
4 16 17 18 19
4 17 18 19 20
3 18 19 20
2 19 20
1 20
0

output:

12884901888

result:

ok single line: '12884901888'

Test #44:

score: 0
Accepted
time: 2ms
memory: 3340kb

input:

20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

output:

1

result:

ok single line: '1'

Subtask #5:

score: 1
Accepted

Test #45:

score: 1
Accepted
time: 0ms
memory: 3360kb

input:

25
24 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
23 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
22 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
21 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
20 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ...

output:

5354228880

result:

ok single line: '5354228880'

Test #46:

score: 0
Accepted
time: 3ms
memory: 3548kb

input:

27
26 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
25 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
24 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
23 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
22 6 7 8 9 10 11 ...

output:

26771144400

result:

ok single line: '26771144400'

Test #47:

score: 0
Accepted
time: 3ms
memory: 3520kb

input:

29
28 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
27 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
26 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
25 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27...

output:

80313433200

result:

ok single line: '80313433200'

Test #48:

score: 0
Accepted
time: 4ms
memory: 3332kb

input:

31
30 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
29 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
28 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
27 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21...

output:

2329089562800

result:

ok single line: '2329089562800'

Test #49:

score: 0
Accepted
time: 2ms
memory: 3472kb

input:

33
32 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
31 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
30 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
29 5 6 7 8 9 10 11 12 13 14 15...

output:

144403552893600

result:

ok single line: '144403552893600'

Test #50:

score: 0
Accepted
time: 0ms
memory: 3464kb

input:

34
1 34
20 4 5 6 10 11 12 13 14 15 17 19 20 22 24 25 26 27 28 30 33
18 4 7 8 9 11 13 15 16 18 20 22 26 27 28 30 31 32 33
18 5 7 10 11 12 13 14 16 17 18 19 20 26 27 28 30 31 33
14 7 8 9 12 13 14 17 18 21 22 25 26 28 30
16 9 10 11 13 15 16 17 18 23 24 25 26 29 31 32 34
19 8 9 11 13 14 16 17 18 20 21 2...

output:

1

result:

ok single line: '1'

Test #51:

score: 0
Accepted
time: 5ms
memory: 3488kb

input:

34
18 2 5 11 14 15 16 18 19 21 22 24 25 26 27 29 31 32 34
17 5 6 7 9 10 12 13 15 16 18 19 21 23 24 26 32 33
14 6 7 9 12 13 14 16 17 19 23 25 27 28 30
11 7 8 10 14 18 21 22 24 25 26 30
13 7 10 15 17 19 24 25 26 28 29 30 31 33
13 8 10 12 15 17 20 21 24 25 27 29 33 34
13 12 16 20 21 22 23 24 25 27 28 3...

output:

823985495927193600

result:

ok single line: '823985495927193600'

Test #52:

score: 0
Accepted
time: 16ms
memory: 3480kb

input:

34
33 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
30 3 4 5 7 8 9 10 11 12 13 14 15 16 17 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
30 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 23 24 25 26 27 28 29 30 31 32 33 34
30 5 6 7 8 9 10 11 12 13 14 1...

output:

1316043101045711215826288640000000000

result:

ok single line: '1316043101045711215826288640000000000'

Test #53:

score: 0
Accepted
time: 2ms
memory: 3456kb

input:

34
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
0

output:

1

result:

ok single line: '1'

Test #54:

score: 0
Accepted
time: 4ms
memory: 3560kb

input:

34
3 2 3 4
3 3 4 5
3 4 5 6
3 5 6 7
3 6 7 8
3 7 8 9
3 8 9 10
3 9 10 11
3 10 11 12
3 11 12 13
3 12 13 14
3 13 14 15
3 14 15 16
3 15 16 17
3 16 17 18
3 17 18 19
3 18 19 20
3 19 20 21
3 20 21 22
3 21 22 23
3 22 23 24
3 23 24 25
3 24 25 26
3 25 26 27
3 26 27 28
3 27 28 29
3 28 29 30
3 29 30 31
3 30 31 32...

output:

617673396283947

result:

ok single line: '617673396283947'

Test #55:

score: 0
Accepted
time: 6ms
memory: 3524kb

input:

34
17 2 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
17 3 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
17 4 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
17 5 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
17 6 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
17 7 19 20 21 22 23 24 25 26 27 ...

output:

596208601546720632677647440

result:

ok single line: '596208601546720632677647440'

Subtask #6:

score: 1
Accepted

Test #56:

score: 1
Accepted
time: 0ms
memory: 3516kb

input:

26
25 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
24 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
23 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
22 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
21 6 7 8 9 10 11 12 13 14 15 ...

output:

26771144400

result:

ok single line: '26771144400'

Test #57:

score: 0
Accepted
time: 4ms
memory: 3476kb

input:

28
27 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
26 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
25 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
24 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
23 6 ...

output:

80313433200

result:

ok single line: '80313433200'

Test #58:

score: 0
Accepted
time: 4ms
memory: 3520kb

input:

30
29 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
28 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
27 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
26 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24...

output:

2329089562800

result:

ok single line: '2329089562800'

Test #59:

score: 0
Accepted
time: 4ms
memory: 3404kb

input:

32
31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
30 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
29 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
28 5 6 7 8 9 10 11 12 13 14 15 16 17 18...

output:

72201776446800

result:

ok single line: '72201776446800'

Test #60:

score: 0
Accepted
time: 4ms
memory: 3400kb

input:

34
33 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
32 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
31 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
30 5 6 7 8 9 10 11 12...

output:

144403552893600

result:

ok single line: '144403552893600'

Test #61:

score: 0
Accepted
time: 3ms
memory: 3404kb

input:

34
17 3 4 5 13 14 15 17 18 19 23 24 27 28 29 30 31 32
20 3 7 10 11 13 16 17 18 19 21 22 23 25 26 27 28 29 30 33 34
14 6 8 10 15 16 17 18 21 24 26 27 29 31 32
15 5 10 11 13 16 18 19 20 21 23 25 30 31 33 34
19 6 10 11 12 13 14 15 17 20 23 24 25 26 27 29 30 32 33 34
11 13 14 15 21 22 23 25 26 28 32 33
...

output:

212878925715456000000

result:

ok single line: '212878925715456000000'

Test #62:

score: 0
Accepted
time: 3ms
memory: 3476kb

input:

34
15 3 4 6 9 10 15 16 17 19 22 23 24 26 28 32
19 3 7 10 11 12 13 14 15 18 19 20 23 25 26 27 28 30 31 33
15 5 6 7 9 13 14 16 18 19 21 23 27 28 30 34
16 6 7 8 9 10 11 13 14 16 18 23 25 26 27 29 33
12 8 12 16 19 21 22 25 27 28 32 33 34
14 7 10 14 15 16 17 23 26 27 30 31 32 33 34
21 9 10 11 12 13 16 17...

output:

127800021888000000

result:

ok single line: '127800021888000000'

Test #63:

score: 0
Accepted
time: 11ms
memory: 3576kb

input:

33
31 2 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
30 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30 31 32 33
30 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
28 6 7 8 9 10 11 12 13 14 15 16 17 ...

output:

49072799824510889298493440000000000

result:

ok single line: '49072799824510889298493440000000000'

Test #64:

score: 0
Accepted
time: 3ms
memory: 3384kb

input:

34
2 2 3
2 3 4
2 4 5
2 5 6
2 6 7
2 7 8
2 8 9
2 9 10
2 10 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 16
2 16 17
2 17 18
2 18 19
2 19 20
2 20 21
2 21 22
2 22 23
2 23 24
2 24 25
2 25 26
2 26 27
2 27 28
2 28 29
2 29 30
2 30 31
2 31 32
2 32 33
2 33 34
1 34
0

output:

4294967296

result:

ok single line: '4294967296'

Test #65:

score: 0
Accepted
time: 8ms
memory: 3516kb

input:

34
17 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
17 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
17 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
17 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
17 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
17 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
17 8 9...

output:

298104300773360316338823720

result:

ok single line: '298104300773360316338823720'

Test #66:

score: 0
Accepted
time: 2ms
memory: 3324kb

input:

34
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

output:

1

result:

ok single line: '1'

Subtask #7:

score: 1
Accepted

Test #67:

score: 1
Accepted
time: 15ms
memory: 3492kb

input:

61
60 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
59 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 ...

output:

9690712164777231700912800

result:

ok single line: '9690712164777231700912800'

Test #68:

score: 0
Accepted
time: 16ms
memory: 3448kb

input:

63
62 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
61 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 ...

output:

591133442051411133755680800

result:

ok single line: '591133442051411133755680800'

Test #69:

score: 0
Accepted
time: 16ms
memory: 3420kb

input:

65
64 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
63 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 ...

output:

1182266884102822267511361600

result:

ok single line: '1182266884102822267511361600'

Test #70:

score: 0
Accepted
time: 17ms
memory: 3460kb

input:

67
66 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
65 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 ...

output:

1182266884102822267511361600

result:

ok single line: '1182266884102822267511361600'

Test #71:

score: 0
Accepted
time: 19ms
memory: 3488kb

input:

69
68 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
67 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 ...

output:

79211881234889091923261227200

result:

ok single line: '79211881234889091923261227200'

Test #72:

score: 0
Accepted
time: 2ms
memory: 3512kb

input:

70
0
38 3 6 8 9 12 13 14 17 19 20 21 22 24 25 29 31 32 33 34 37 38 40 44 45 47 48 49 50 55 56 57 61 62 65 67 68 69 70
41 4 5 6 8 11 12 16 17 18 19 21 22 23 24 25 26 27 28 30 31 32 34 35 36 37 39 40 44 45 46 47 50 52 53 57 59 60 61 62 65 70
39 6 7 9 10 11 14 16 17 18 20 22 24 25 26 28 29 31 32 33 34 ...

output:

1

result:

ok single line: '1'

Test #73:

score: 0
Accepted
time: 65ms
memory: 3496kb

input:

70
29 3 7 8 10 11 17 21 25 26 27 28 29 31 35 36 38 39 43 44 45 47 49 50 51 52 55 56 62 66
35 4 5 7 8 9 10 11 14 15 20 22 23 24 25 27 30 33 34 35 36 38 41 42 44 46 49 50 51 52 55 56 57 65 69 70
37 4 6 7 8 9 10 11 13 14 17 18 22 23 24 25 26 28 30 32 35 39 40 44 45 47 50 51 52 53 55 59 62 64 65 68 69 7...

output:

3006608807500305953434444076444105103915142348800000000000

result:

ok single line: '3006608807500305953434444076444105103915142348800000000000'

Test #74:

score: 0
Accepted
time: 257ms
memory: 3424kb

input:

70
69 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
68 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ...

output:

6110351863510125990264388615433718525280551915548715438709969038452927274829221281660928000000000

result:

ok single line: '611035186351012599026438861543...2927274829221281660928000000000'

Test #75:

score: 0
Accepted
time: 2ms
memory: 3444kb

input:

70
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61
1 62
...

output:

1

result:

ok single line: '1'

Test #76:

score: 0
Accepted
time: 10ms
memory: 3504kb

input:

70
3 2 3 4
3 3 4 5
3 4 5 6
3 5 6 7
3 6 7 8
3 7 8 9
3 8 9 10
3 9 10 11
3 10 11 12
3 11 12 13
3 12 13 14
3 13 14 15
3 14 15 16
3 15 16 17
3 16 17 18
3 17 18 19
3 18 19 20
3 19 20 21
3 20 21 22
3 21 22 23
3 22 23 24
3 23 24 25
3 24 25 26
3 25 26 27
3 26 27 28
3 27 28 29
3 28 29 30
3 29 30 31
3 30 31 32...

output:

92709463147897837085761925410587

result:

ok single line: '92709463147897837085761925410587'

Test #77:

score: 0
Accepted
time: 48ms
memory: 3508kb

input:

70
35 2 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
35 3 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
35 4 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 ...

output:

909748571420442737454132893901933983744401484727859497070312500000

result:

ok single line: '909748571420442737454132893901...3744401484727859497070312500000'

Subtask #8:

score: 1
Accepted

Test #78:

score: 1
Accepted
time: 17ms
memory: 3376kb

input:

62
61 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
60 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 ...

output:

591133442051411133755680800

result:

ok single line: '591133442051411133755680800'

Test #79:

score: 0
Accepted
time: 18ms
memory: 3492kb

input:

64
63 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
62 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 ...

output:

591133442051411133755680800

result:

ok single line: '591133442051411133755680800'

Test #80:

score: 0
Accepted
time: 17ms
memory: 3588kb

input:

66
65 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
64 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ...

output:

1182266884102822267511361600

result:

ok single line: '1182266884102822267511361600'

Test #81:

score: 0
Accepted
time: 16ms
memory: 3416kb

input:

68
67 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
66 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 ...

output:

79211881234889091923261227200

result:

ok single line: '79211881234889091923261227200'

Test #82:

score: 0
Accepted
time: 20ms
memory: 3376kb

input:

70
69 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
68 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ...

output:

79211881234889091923261227200

result:

ok single line: '79211881234889091923261227200'

Test #83:

score: 0
Accepted
time: 61ms
memory: 3460kb

input:

70
36 2 3 6 9 12 13 14 15 16 17 19 21 22 23 26 27 29 32 34 35 36 38 40 41 42 43 50 52 55 56 60 61 66 67 68 70
36 7 9 11 12 13 14 15 16 20 23 24 25 26 30 31 33 36 37 41 42 43 45 46 48 49 50 51 53 58 59 60 63 64 66 69 70
36 4 5 6 7 8 19 20 21 22 24 25 26 29 30 33 37 42 43 44 45 46 47 49 51 52 53 54 55...

output:

1824698728666414725003035970578753465043319435296768000

result:

ok single line: '1824698728666414725003035970578753465043319435296768000'

Test #84:

score: 0
Accepted
time: 60ms
memory: 3488kb

input:

70
32 3 5 7 9 12 14 16 17 24 28 30 32 33 34 35 36 37 40 43 45 48 51 54 55 56 60 62 63 64 65 67 70
35 5 7 8 10 11 13 15 16 20 21 22 24 25 27 28 29 32 34 37 38 42 44 46 47 48 49 50 52 53 56 59 60 63 64 67
33 8 9 12 13 15 16 19 20 21 23 24 25 26 28 29 30 33 35 37 38 40 41 44 47 48 51 52 53 55 61 63 65 ...

output:

4292173931626051091770885709822461476864000000000000000

result:

ok single line: '4292173931626051091770885709822461476864000000000000000'

Test #85:

score: 0
Accepted
time: 244ms
memory: 3424kb

input:

69
67 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
66 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 ...

output:

238263644444283524626746182787195320596947770908655273237837523431337976495299624960000000000000

result:

ok single line: '238263644444283524626746182787...1337976495299624960000000000000'

Test #86:

score: 0
Accepted
time: 6ms
memory: 3364kb

input:

70
2 2 3
2 3 4
2 4 5
2 5 6
2 6 7
2 7 8
2 8 9
2 9 10
2 10 11
2 11 12
2 12 13
2 13 14
2 14 15
2 15 16
2 16 17
2 17 18
2 18 19
2 19 20
2 20 21
2 21 22
2 22 23
2 23 24
2 24 25
2 25 26
2 26 27
2 27 28
2 28 29
2 29 30
2 30 31
2 31 32
2 32 33
2 33 34
2 34 35
2 35 36
2 36 37
2 37 38
2 38 39
2 39 40
2 40 41
...

output:

295147905179352825856

result:

ok single line: '295147905179352825856'

Test #87:

score: 0
Accepted
time: 79ms
memory: 3472kb

input:

70
37 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
37 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
37 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ...

output:

135545006439836585025034751502731044225949367886838081195397553200

result:

ok single line: '135545006439836585025034751502...4225949367886838081195397553200'

Test #88:

score: 0
Accepted
time: 2ms
memory: 3408kb

input:

70
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

output:

1

result:

ok single line: '1'

Subtask #9:

score: 0
Time Limit Exceeded

Test #89:

score: 1
Accepted
time: 49ms
memory: 3368kb

input:

91
90 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
89 3 4 5 6 7 8 9 10 11 12 13 14 ...

output:

718766754945489455304472257065075294400

result:

ok single line: '718766754945489455304472257065075294400'

Test #90:

score: 0
Accepted
time: 51ms
memory: 3584kb

input:

93
92 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
91 3 4 5 6 7 8 9 10 11 12 ...

output:

718766754945489455304472257065075294400

result:

ok single line: '718766754945489455304472257065075294400'

Test #91:

score: 0
Accepted
time: 47ms
memory: 3332kb

input:

95
94 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
93 3 4 5 6 7 8 9 10 ...

output:

718766754945489455304472257065075294400

result:

ok single line: '718766754945489455304472257065075294400'

Test #92:

score: 0
Accepted
time: 54ms
memory: 3556kb

input:

97
96 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
95 3 4 5 6 7 8...

output:

718766754945489455304472257065075294400

result:

ok single line: '718766754945489455304472257065075294400'

Test #93:

score: 0
Accepted
time: 60ms
memory: 3480kb

input:

99
98 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
97 3 4 5...

output:

69720375229712477164533808935312303556800

result:

ok single line: '69720375229712477164533808935312303556800'

Test #94:

score: 0
Accepted
time: 1ms
memory: 3428kb

input:

100
0
42 3 6 7 8 10 11 14 15 20 25 26 29 30 31 32 35 37 38 39 40 41 44 46 48 49 51 53 64 66 69 72 74 75 79 82 85 86 89 91 93 95 98
58 6 9 10 11 12 14 17 19 20 21 23 27 30 31 33 34 35 38 39 41 42 44 47 49 51 52 53 54 55 56 59 60 61 62 63 64 65 70 71 72 73 74 75 76 78 79 80 83 86 88 89 91 92 94 95 96 ...

output:

1

result:

ok single line: '1'

Test #95:

score: 0
Accepted
time: 334ms
memory: 3440kb

input:

100
53 2 4 5 6 14 15 16 17 19 20 21 22 23 25 26 30 31 32 33 36 37 42 45 46 47 48 51 52 53 58 59 60 63 64 66 68 70 71 72 73 76 77 81 85 87 89 90 92 93 94 96 99 100
47 3 5 7 8 9 11 12 14 16 18 19 21 25 30 33 36 38 39 40 42 55 57 58 59 60 63 65 67 69 70 72 75 76 77 79 82 83 86 87 89 90 91 92 94 97 98 1...

output:

9786972101604507013106867288561142873316903715389112559544703036711489911092160757760000000000000000

result:

ok single line: '978697210160450701310686728856...9911092160757760000000000000000'

Test #96:

score: -1
Time Limit Exceeded

input:

100
99 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
96 ...

output:


result:


Subtask #10:

score: 0
Time Limit Exceeded

Test #101:

score: 1
Accepted
time: 50ms
memory: 3512kb

input:

92
91 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
90 3 4 5 6 7 8 9 10 11 12 13 ...

output:

718766754945489455304472257065075294400

result:

ok single line: '718766754945489455304472257065075294400'

Test #102:

score: 0
Accepted
time: 54ms
memory: 3516kb

input:

94
93 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
92 3 4 5 6 7 8 9 10 11 ...

output:

718766754945489455304472257065075294400

result:

ok single line: '718766754945489455304472257065075294400'

Test #103:

score: 0
Accepted
time: 48ms
memory: 3476kb

input:

96
95 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
94 3 4 5 6 7 8 9 ...

output:

718766754945489455304472257065075294400

result:

ok single line: '718766754945489455304472257065075294400'

Test #104:

score: 0
Accepted
time: 55ms
memory: 3368kb

input:

98
97 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
96 3 4 5 6 ...

output:

69720375229712477164533808935312303556800

result:

ok single line: '69720375229712477164533808935312303556800'

Test #105:

score: 0
Accepted
time: 61ms
memory: 3552kb

input:

100
99 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
98 ...

output:

69720375229712477164533808935312303556800

result:

ok single line: '69720375229712477164533808935312303556800'

Test #106:

score: 0
Accepted
time: 292ms
memory: 3492kb

input:

100
59 4 6 7 8 13 14 15 16 17 18 19 23 24 25 28 30 33 36 37 38 39 40 42 47 48 49 50 51 53 54 55 57 58 59 60 62 64 65 71 72 73 74 75 77 79 81 83 85 86 87 88 89 90 91 92 94 95 97 100
47 6 7 9 10 11 12 13 16 18 20 21 22 24 26 27 28 29 30 33 34 35 36 37 38 45 46 49 51 52 55 58 59 60 64 68 69 70 77 78 79...

output:

3234726786449602891204829903955562501789987685018148002760129838455776423706624000000000000

result:

ok single line: '323472678644960289120482990395...9838455776423706624000000000000'

Test #107:

score: 0
Accepted
time: 263ms
memory: 3388kb

input:

100
49 3 7 9 13 19 20 21 22 23 24 27 28 32 33 39 40 42 45 46 50 51 52 53 58 60 62 63 64 68 69 71 73 74 77 78 79 80 81 82 85 89 90 91 92 95 97 98 99 100
52 3 4 7 9 13 19 20 21 25 27 29 30 32 35 36 38 42 43 44 48 49 50 51 54 57 59 62 64 65 66 67 68 72 74 76 77 79 80 82 83 84 85 87 89 90 92 93 94 95 96...

output:

12035423866774135891802479437916178642965091716536677250621997642966471016448000000000000

result:

ok single line: '120354238667741358918024794379...1997642966471016448000000000000'

Test #108:

score: -1
Time Limit Exceeded

input:

99
98 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
96 3 4 5...

output:


result: