QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#803000#9863. Bracketsjapan406364961 (Ryo Takahashi, Masanori Ogiwara, Takuto Koriyama)#AC ✓295ms117728kbC++206.7kb2024-12-07 15:34:022024-12-10 04:37:58

Judging History

This is the latest submission verdict.

  • [2024-12-10 04:37:58]
  • 自动重测本题所有获得100分的提交记录
  • Verdict: AC
  • Time: 295ms
  • Memory: 117728kb
  • [2024-12-10 04:34:15]
  • hack成功,自动添加数据
  • (/hack/1275)
  • [2024-12-07 15:34:06]
  • Judged
  • Verdict: 100
  • Time: 330ms
  • Memory: 117696kb
  • [2024-12-07 15:34:02]
  • Submitted

answer

#include<iostream>
#include<algorithm>
#include<array>
#include<vector>
#include<chrono>
#include<random>
#include<cassert>
using namespace std;
//https://nyaannyaan.github.io/library/internal/internal-hash.hpp

namespace internal{
using i64 = long long;
using u64 = unsigned long long;
using u128 = __uint128_t;

template <int BASE_NUM = 2>
struct Hash : array<u64, BASE_NUM> {
  using array<u64, BASE_NUM>::operator[];
  static constexpr int n = BASE_NUM;

  Hash() : array<u64, BASE_NUM>() {}

  static constexpr u64 md = (1ull << 61) - 1;

  constexpr static Hash set(const i64 &a) {
    Hash res;
    fill(begin(res), end(res), cast(a));
    return res;
  }
  Hash &operator+=(const Hash &r) {
    for (int i = 0; i < n; i++)
      if (((*this)[i] += r[i]) >= md) (*this)[i] -= md;
    return *this;
  }
  Hash &operator+=(const i64 &r) {
    u64 s = cast(r);
    for (int i = 0; i < n; i++)
      if (((*this)[i] += s) >= md) (*this)[i] -= md;
    return *this;
  }
  Hash &operator-=(const Hash &r) {
    for (int i = 0; i < n; i++)
      if (((*this)[i] += md - r[i]) >= md) (*this)[i] -= md;
    return *this;
  }
  Hash &operator-=(const i64 &r) {
    u64 s = cast(r);
    for (int i = 0; i < n; i++)
      if (((*this)[i] += md - s) >= md) (*this)[i] -= md;
    return *this;
  }
  Hash &operator*=(const Hash &r) {
    for (int i = 0; i < n; i++) (*this)[i] = modmul((*this)[i], r[i]);
    return *this;
  }
  Hash &operator*=(const i64 &r) {
    u64 s = cast(r);
    for (int i = 0; i < n; i++) (*this)[i] = modmul((*this)[i], s);
    return *this;
  }

  Hash operator+(const Hash &r) { return Hash(*this) += r; }
  Hash operator+(const i64 &r) { return Hash(*this) += r; }
  Hash operator-(const Hash &r) { return Hash(*this) -= r; }
  Hash operator-(const i64 &r) { return Hash(*this) -= r; }
  Hash operator*(const Hash &r) { return Hash(*this) *= r; }
  Hash operator*(const i64 &r) { return Hash(*this) *= r; }
  Hash operator-() const {
    Hash res;
    for (int i = 0; i < n; i++) res[i] = (*this)[i] == 0 ? 0 : md - (*this)[i];
    return res;
  }
  friend Hash pfma(const Hash &a, const Hash &b, const Hash &c) {
    Hash res;
    for (int i = 0; i < n; i++) res[i] = modfma(a[i], b[i], c[i]);
    return res;
  }
  friend Hash pfma(const Hash &a, const Hash &b, const i64 &c) {
    Hash res;
    u64 s = cast(c);
    for (int i = 0; i < n; i++) res[i] = modfma(a[i], b[i], s);
    return res;
  }

  Hash pow(long long e) {
    Hash a{*this}, res{Hash::set(1)};
    for (; e; a *= a, e >>= 1) {
      if (e & 1) res *= a;
    }
    return res;
  }

  static Hash get_basis() {
    static auto rand_time =
        chrono::duration_cast<chrono::nanoseconds>(
            chrono::high_resolution_clock::now().time_since_epoch())
            .count();
    static mt19937_64 rng(rand_time);
    Hash h;
    for (int i = 0; i < n; i++) {
      while (isPrimitive(h[i] = rng() % (md - 1) + 1) == false)
        ;
    }
    return h;
  }

 private:
  static u64 modpow(u64 a, u64 b) {
    u64 r = 1;
    for (a %= md; b; a = modmul(a, a), b >>= 1) r = modmul(r, a);
    return r;
  }
  static bool isPrimitive(u64 x) {
    for (auto &d : vector<u64>{2, 3, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321})
      if (modpow(x, (md - 1) / d) <= 1) return false;
    return true;
  }
  static inline constexpr u64 cast(const long long &a) {
    return a < 0 ? a + md : a;
  }
  static inline constexpr u64 modmul(const u64 &a, const u64 &b) {
    u128 d = u128(a) * b;
    u64 ret = (u64(d) & md) + u64(d >> 61);
    return ret >= md ? ret - md : ret;
  }
  static inline constexpr u64 modfma(const u64 &a, const u64 &b, const u64 &c) {
    u128 d = u128(a) * b + c;
    u64 ret = (d >> 61) + (u64(d) & md);
    return ret >= md ? ret - md : ret;
  }
};

}
/**
 * @brief 繝上ャ繧キ繝・讒矩€菴・ * @docs docs/internal/internal-hash.md
 */

using Hash=internal::Hash<2>;
Hash basis=Hash::get_basis();
Hash pw[5<<17];
int N,M;
pair<vector<pair<int,Hash> >,vector<pair<int,int> > >calc(vector<pair<int,bool> >SH,vector<vector<int> >RtoL)
{
	assert(SH.size()==N);
	assert(RtoL.size()==N+1);
	assert(RtoL[0].empty());
	vector<Hash>cur;
	vector<int>bra,idx;
	cur.push_back(Hash::set(0));
	bra.push_back(-1);
	idx.push_back(0);
	vector<int>depth(N+1);
	depth[0]=0;
	vector<pair<int,Hash> >L;
	vector<pair<int,int> >S;
	for(int r=1;r<=N;r++)
	{
		if(SH[r-1].second)
		{//close
			depth[r]=depth[r-1]-1;
			if(bra.back()==SH[r-1].first)
			{
				bra.pop_back();
				cur.pop_back();
				idx.pop_back();
			}
			else
			{
				bra.clear();
				cur.clear();
				idx.clear();
				cur.push_back(Hash::set(0));
				bra.push_back(-1);
				idx.push_back(r);
			}
		}
		else
		{//open
			depth[r]=depth[r-1]+1;
			bra.push_back(SH[r-1].first);
			cur.push_back(cur.back()*basis+Hash::set(SH[r-1].first));
			idx.push_back(r);
		}
		for(int l:RtoL[r])
		{
			if(depth[l]>depth[r])continue;
			if(depth[l]==depth[r])
			{
				if(idx.back()<=l)S.push_back(make_pair(l,r));
			}
			else
			{
				int d=depth[r]-depth[l];
				assert(d>=1);
				if(cur.size()<=d)continue;
				if(idx[idx.size()-d-1]<=l&&idx[idx.size()-d]>l)
				{
					L.push_back(make_pair(d,cur.back()-cur[cur.size()-d-1]*pw[d]));
				}
			}
		}
	}
	return make_pair(L,S);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	pw[0]=Hash::set(1);
	for(int i=1;i<5<<17;i++)pw[i]=pw[i-1]*basis;
	int T;cin>>T;
	for(;T--;)
	{
		string S;
		cin>>N>>M>>S;
		vector<pair<int,bool> >SH(N);
		for(int i=0;i<N;i++)
		{
			if(S[i]=='(')SH[i]=make_pair(1,false);
			else if(S[i]==')')SH[i]=make_pair(1,true);
			else if(S[i]=='[')SH[i]=make_pair(2,false);
			else if(S[i]==']')SH[i]=make_pair(2,true);
			else if(S[i]=='{')SH[i]=make_pair(3,false);
			else if(S[i]=='}')SH[i]=make_pair(3,true);
			else if(S[i]=='<')SH[i]=make_pair(4,false);
			else if(S[i]=='>')SH[i]=make_pair(4,true);
			else assert(false);
		}
		vector<vector<int> >LtoR(N+1),RtoL(N+1);
		for(int i=0;i<M;i++)
		{
			int l,r;cin>>l>>r;
			l--;
			LtoR[N-l].push_back(N-r);
			RtoL[r].push_back(l);
		}
		auto[L,SL]=calc(SH,RtoL);
		reverse(SH.begin(),SH.end());
		for(int i=0;i<N;i++)SH[i].second=!SH[i].second;
		auto[R,SR]=calc(SH,LtoR);
		sort(SL.begin(),SL.end());
		for(int i=0;i<SR.size();i++)
		{
			auto[l,r]=SR[i];
			SR[i]=make_pair(N-r,N-l);
		}
		sort(SR.begin(),SR.end());
		assert(SL==SR);
		int ans=SL.size()/2;
		{
			sort(L.begin(),L.end());
			sort(R.begin(),R.end());
			int li=0,ri=0;
			while(li<L.size()&&ri<R.size())
			{
				if(L[li]==R[ri])ans++,li++,ri++;
				else if(L[li]<R[ri])li++;
				else ri++;
			}
		}
		cout<<ans<<"\n";
	}
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 14072kb

input:

4
8 1
()[]{}<>
3 6
2 6
)(
1 1
1 1
1 1
2 2
2 2
2 2
6 2
([)(])
1 3
4 6
22 8
([{}<<<<])>>>>([]){()}
3 8
11 14
1 10
3 4
19 22
20 21
17 20
21 22

output:

0
3
0
2

result:

ok 4 number(s): "0 3 0 2"

Test #2:

score: 0
Accepted
time: 157ms
memory: 13860kb

input:

10000
50 50
]][][>([<)}{>(([<<>[]}[}>(}([}[><[}<[}<<(]]<>[]>)<
16 50
19 31
6 34
19 49
14 44
26 49
10 43
28 49
13 16
23 39
4 26
30 43
20 27
10 20
25 44
12 42
27 34
2 8
29 44
11 42
18 42
1 4
1 47
31 31
26 47
22 44
16 35
15 48
35 41
17 20
11 13
20 21
9 45
13 46
33 47
35 46
22 26
2 37
14 39
34 34
41 44
...

output:

0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
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
1
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
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
2
1
0
0
0
0
1
0
0
0
0
...

result:

ok 10000 numbers

Test #3:

score: 0
Accepted
time: 71ms
memory: 13956kb

input:

1000
50 500
[]]})<{>]){[[><>[{](}}{<(<)<{]{><><}>([[{(}(><}>{]
25 46
19 30
23 41
27 34
5 11
8 42
40 46
24 34
7 47
44 45
13 13
9 44
18 32
12 23
24 38
35 49
31 36
14 46
2 9
7 44
27 41
15 22
42 44
21 49
27 50
28 36
6 26
15 47
22 40
6 25
25 43
5 45
19 19
10 40
6 20
30 36
39 44
14 32
17 31
7 47
24 34
2 8...

output:

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

result:

ok 1000 numbers

Test #4:

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

input:

100
50 5000
[)[){>})}>>][<>}[{{))}<(<]}[})>>})<)[((({}<}>}}>[[
38 49
47 48
43 46
5 50
8 11
21 29
11 32
8 8
9 13
1 18
35 48
12 12
24 45
6 19
13 42
30 37
23 41
17 21
40 43
3 31
3 11
9 31
17 35
1 49
9 50
43 47
1 9
8 43
11 19
40 47
6 42
7 31
23 37
30 46
5 30
33 38
8 25
21 39
1 1
27 31
15 35
9 11
7 37
26...

output:

54
99
81
80
54
68
58
33
67
78
73
78
86
95
74
46
101
99
89
82
85
57
53
96
112
76
91
72
42
78
98
72
77
106
63
76
60
91
83
68
64
69
106
77
81
66
41
73
93
61
58
55
63
51
43
78
48
71
134
64
69
112
53
73
61
50
80
91
79
63
75
80
49
62
75
80
78
54
59
48
55
73
63
71
69
94
69
51
87
68
69
102
61
70
61
80
54
62...

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 44ms
memory: 14656kb

input:

10
50 50000
[(>><<)>][<]<>>>]{>{>{<({>[[(>[[<{)>]()>[{}]))}>[(
15 24
12 46
2 21
3 38
13 31
3 29
24 37
11 27
11 24
21 42
14 15
15 23
15 45
11 19
17 45
2 16
38 49
9 32
18 30
17 46
29 35
16 24
16 44
31 50
37 45
25 50
39 46
14 46
45 50
21 36
6 14
16 39
38 47
21 22
22 32
14 46
5 31
39 41
37 48
23 33
10 1...

output:

804
1376
493
630
817
973
747
761
810
694

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 44ms
memory: 22076kb

input:

1
50 500000
({>([[[]>)>)[)(<<[}({]>{){<[}}{{}}(]){{[>)()<{{]{}
39 42
2 15
13 38
8 15
39 50
2 11
9 33
11 47
28 39
26 29
7 33
38 39
19 25
3 24
11 38
6 30
7 32
8 34
12 50
21 27
26 39
20 46
27 32
46 48
30 41
22 48
32 37
17 26
28 31
23 29
24 40
10 43
28 49
39 45
40 45
24 28
11 29
10 27
21 31
10 18
1 38
7...

output:

9905

result:

ok 1 number(s): "9905"

Test #7:

score: 0
Accepted
time: 136ms
memory: 14216kb

input:

1000
500 500
)<}]<{>((]>]<[}}[}>{[]][[((}(}<<>])[}{[{{[<){<}[([{}}>{}<((<[}][{[(<[}(}>]({[]({})}{<}>})[{{{>]]))[>(>)][}}}>[<{))((>{<[]{[>{[>)}[(<{]}>{(}[])>)}]()>{({{({>{><}({([>>}(}{)}<[]]><[(<}}]}}[}]{(}[>{][}(<}[><)}]]))(]{(<(}][()]}{{{{){{<[{))]](<(]>({[{)[{]<(>]<>}[<{<}([])><{}{[]}}[>))[[]}<]}[...

output:

0
0
1
0
0
1
0
0
1
0
0
1
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000 numbers

Test #8:

score: 0
Accepted
time: 74ms
memory: 14212kb

input:

100
500 5000
}(>]<{[>}>)(><<})(}<[](]{}]<<]>{{}]>}(<>{]>{)[<<}<(<)]<[>)<{>{){{{][}<>}{((<[))})><])>)>{(<[)(>[{<([}<{)})<>{[)]<))>){([()[}]<)>}[))}(}]}])}<}}>[<()){]]}}[>}<>[}>>>}}[]<>>[([<)>}{[)}]])[>>()[]<(([}{{[><[}][[){>{([[<)>[>}[}(]([<{<}[>(>(<<]]()[(}[(<}{}{)}{]()>({>){[[[{<)>({>(((])[>[)<{(}]...

output:

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

result:

ok 100 numbers

Test #9:

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

input:

10
500 50000
]}){>(](][]>>[]}>{(>][](<)]((([({}{>[>](<{}[>}{>)<}}{>[([}(<})[)<({)>)(>][{]({[({[([}<<>>{[][}>[[<)[}<]<)]){]<<(([(>()>}<>)>[})[>>][}>[{((]{>]>><}}]{>}[<}<][())}{][<[>)(>[{{]}<{{><)()>><><{<}>{{()())}[[<][>){{}>)(})])]<)>>(}}>[>]])(}((([<[[}[{](}><{[][]{>[<<[{>)}]))><[((<([<])(]()}{]({{...

output:

104
101
118
107
118
122
136
107
109
113

result:

ok 10 numbers

Test #10:

score: 0
Accepted
time: 50ms
memory: 21004kb

input:

1
500 500000
<[)[}](<}[{}>{>>()(><>){>>>([<<{]}][{[([>}]}}{<}[>)]<{{(}{<}({)[[<[]{}<<[{(<{({]<)(((}}{<<[)(>)({[)]>}[[(({><(([{(}}{]}()]}<]}(>>]}}}(}>((<()}[(}]([[}[}<}<{((<<}(><{(}]]]<)(<]>([[(]]<[<]})(>)}})(><}}(>{{](])<}}[}<}(>>}]>)]]{><>)[}[<<()}]}<<{{(]]{)}]{>}}[]]{(}])[<]>){>(])}<(})]>([[>)]]<)...

output:

1109

result:

ok 1 number(s): "1109"

Test #11:

score: 0
Accepted
time: 135ms
memory: 14644kb

input:

100
5000 5000
[][]}(<{>{(](}]>}<>}(]<}})(]<]>>(<{}{<(<><{<[}[{[{){)){(]<{]][[}]><[>[]]]>(](]([{(]<<{]<<[(}]>{}]<()>}})]<{[]>>{)[}[(<[}{{{[>[>><{[[[<([(]){))<>]]((<})>>{)(({]]<>}}[}{})<}>{[}}))](({(]<[<)}]<[[)([<[>[<([}])}{]><]<(([)>]{<)[]])][<<][(((<><}<)[)((]([)[([{<<<>(>{]>>{}<}(<)}]{{}>>{(}}]<)<(...

output:

0
0
2
1
0
0
0
0
0
0
0
0
1
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
1
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
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 100 numbers

Test #12:

score: 0
Accepted
time: 74ms
memory: 15352kb

input:

10
5000 50000
}}>]]}][()]]{)(>)[)>({>{{}>}{}]{<())>>[}]>{)]()}[><)({}>>}]<))[)><(<]{>(>(]<{[>)}>([)>(){({><)>}[(}])})[}}>[<>[}([>[]<)][<]>}{))>}>>()(]]{(<)(](}){)>><{)(><}](]{}<[(({{]>>)<{([{]<({{){[{(}<{{}])]{)]<{{<]]{]]{](}<[{[]{{>]()<<](}<{(}]>>{{]<{}{()])>>[>>[({)}>{[{<()))[{[}]{)}<{]([<[(]<]{)}...

output:

7
3
8
9
8
7
5
6
3
8

result:

ok 10 numbers

Test #13:

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

input:

1
5000 500000
>([><])])><{<>)(>[>()]>[)[<<[){[(>}<()[)}{}[}{(>[)>[[})<(>]<([}><>[[(>}]()>{][[[{()>)<}>}{[]}{>)]<[)<{[[(>]]>(}[{(})>)]])[]{(<{><<{}]]){>})<)<]<[({>[]{{[><)))])(}(}})]]{][})}{<>(}){}>[]<{[(]}>(<<)<(>>>){(>{<][()>{({]){{><<()}<<[<>}<(>)({]]]](<[]]])<]<)[)<([>)>]<<[(<){>[[([)<)>>}]()[>{}...

output:

117

result:

ok 1 number(s): "117"

Test #14:

score: 0
Accepted
time: 163ms
memory: 21292kb

input:

10
50000 50000
][[<(}{{[{[<<(<}>)[<[)))][]}<]}[>>>}[}{({)}>>[>{[[(]>)<>{[(][}][)]<([}<>]<]]>{)<{](}][}(]]><}>[>)(>()<[])]]{}><}]{]]{[<<(}(}>[{((<]{<>(]}(})[[}()<>}{])(]<](<}(}}]){)()>(<)[{}<>}><]]}>>{((>{(<<()))[){>({((}()]>)(<><>){[(]({>{)>])[]){>[))}{>[>]]{[()([{[][([<)<(<(}(}}({>[(>><<)>][<]<>>>]...

output:

0
0
0
1
0
1
0
0
0
0

result:

ok 10 numbers

Test #15:

score: 0
Accepted
time: 104ms
memory: 27924kb

input:

1
50000 500000
<<[})>}]{]}{>)]]{{{}){(])<{{]((()<[<]([>[){(}[){>}<(<[]<<}{[{<{({><{{[[(<)<[[{[])<])]()}[}(<}{]}<[{>{}<<[[{(<><<][]<>([[<<>>}{}>(<<>{)}[}{{{[{<>{<<[])<}))[<{<[>(]]}]>>](>(}}[)}{{}[}]<{]}>)](]](){([<{)[{(]>)>){[>>>>)){[([){<}>(((><}{[)[>([))]]}[){>]})}(})}}<)><{((}]((>)]}>){}[)[)[{({{[...

output:

5

result:

ok 1 number(s): "5"

Test #16:

score: 0
Accepted
time: 232ms
memory: 85772kb

input:

1
500000 500000
>}<(]){){[<)<[)(<[<})<)>]}]>)[[](<{}]]>[([{{{<>(]>))()<]][((<>[>(>}([<<){{<{){)><}([>{>}](>>]}}(>[)((](}>>])}]<[)}))})]])([]>{]<}<)}<(<>)]]{)]<]]}>}]([>>)({[}})]]](]><}])>{]{)){>><(>{){])]}>[[([)>(([)](<)<<({}][{{()>)>}<<[]({[]{]))[]((]>[[{}>)(>[[]{]}>><<]>]>><{{)])}](>>[{}]))<<{>)(}...

output:

0

result:

ok 1 number(s): "0"

Test #17:

score: 0
Accepted
time: 167ms
memory: 51996kb

input:

1
50000 500000
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

208440

result:

ok 1 number(s): "208440"

Test #18:

score: 0
Accepted
time: 114ms
memory: 17056kb

input:

10
5000 50000
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

20871
20772
20815
20864
20869
20894
20859
20778
20929
20988

result:

ok 10 numbers

Test #19:

score: 0
Accepted
time: 103ms
memory: 14248kb

input:

100
500 5000
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()))))))))))))))))))))))))))))))))))))...

output:

2098
2095
2104
2080
2090
2048
2090
2092
2063
2099
2110
2083
2083
2084
2066
2077
2069
2128
2097
2054
2056
2094
2076
2062
2061
2060
2103
2086
2116
2061
2090
2099
2075
2097
2084
2115
2113
2141
2025
2124
2080
2056
2086
2079
2074
2094
2069
2066
2135
2117
2067
2099
2081
2082
2086
2090
2083
2080
2093
2082
...

result:

ok 100 numbers

Test #20:

score: 0
Accepted
time: 91ms
memory: 13968kb

input:

1000
50 500
((((((((((((((((((((((((()))))))))))))))))))))))))
16 37
28 47
8 41
13 47
6 9
7 11
22 27
14 18
29 45
7 43
34 45
5 29
24 28
5 26
24 46
3 11
1 13
27 40
10 43
34 40
3 48
40 50
22 42
10 40
1 24
10 42
17 24
6 24
26 45
7 38
1 32
9 39
22 43
14 50
9 47
11 39
14 17
5 28
28 42
7 44
27 34
7 11
27 2...

output:

204
198
212
215
203
200
209
197
194
207
203
196
214
216
204
196
205
207
207
202
206
199
208
208
206
213
209
211
209
211
211
211
195
209
213
215
195
199
213
196
198
203
214
208
212
216
205
216
210
216
199
196
208
213
217
212
214
209
201
207
218
204
206
199
211
208
204
213
200
214
205
220
206
215
208
...

result:

ok 1000 numbers

Test #21:

score: 0
Accepted
time: 78ms
memory: 14080kb

input:

10000
5 50
(()))
3 3
4 5
3 5
4 5
2 5
3 5
4 5
1 3
5 5
2 3
2 5
3 5
1 5
4 5
1 3
3 3
2 5
1 5
2 5
1 2
2 5
2 2
1 5
4 5
2 4
5 5
5 5
2 5
2 2
1 2
3 5
2 5
1 5
2 5
2 3
4 5
1 3
4 5
2 2
4 5
3 3
1 4
3 4
1 3
1 4
2 4
2 4
5 5
5 5
1 4
5 50
(()))
3 3
3 4
4 5
2 4
3 4
1 2
2 5
3 5
1 2
1 1
4 4
4 5
5 5
1 2
4 4
2 4
3 5
3 4
...

output:

11
13
17
14
14
11
19
13
14
22
14
9
16
19
14
13
11
13
16
16
19
16
16
14
10
16
15
17
18
19
14
16
17
17
17
19
20
12
12
12
21
13
16
13
16
14
13
19
16
13
16
18
15
19
15
15
19
13
15
15
11
13
18
17
9
15
21
14
17
17
12
13
15
11
16
17
13
13
12
15
11
16
20
21
16
14
14
14
16
12
20
17
12
17
19
15
19
15
16
14
20...

result:

ok 10000 numbers

Test #22:

score: 0
Accepted
time: 238ms
memory: 110776kb

input:

1
500000 500000
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

248787

result:

ok 1 number(s): "248787"

Test #23:

score: 0
Accepted
time: 276ms
memory: 92876kb

input:

1
500000 500000
[}<(>[<[([)]{(()}{(>][)])[[(<[][<>){>(}}{]}<}<[<}>)<]{[<[}{<(}><]{(<>>(<)><((<()<}<{])(<[)[]][>(>]]>>)(<<{[([(][><(>{()}](}<}[{({}]}(}{{]{]<}}[)((}){)>[}){>(]}>[(>[){{((<([({}>)}()}})}<{>>]>[]><>}[{([<])}]}{]]{<>>](>([<}<<]<}<{<]>(]{[><<)(}}}({(][>[[[)[<)(]({<}}}[[[(}[<><>)><[})}{{[]...

output:

53182

result:

ok 1 number(s): "53182"

Test #24:

score: 0
Accepted
time: 249ms
memory: 89048kb

input:

1
500000 500000
](([>{)<([(]>[>)]]>{]<)}}{<>]](])}<{(({{<>(}{>>)<]<]>)){[]>>[>]{]>})<[>{)))[}]<{<)}}>[(}])()}[>()({>)[]<)[[)[}<)]}{(][((){)}{]]<{(](>)>]{){]{}<(](]<{((<[<]]([><[}]][<][{<<>[]<)()]>){(<(>{{((])})])))>]()>}{(<})(])[<)([}<>{{(<{]]({[{<(][}[]>]>}]<><)})[)}}<{}({][][){}]{>{{(](({})}[{]}]{...

output:

5475

result:

ok 1 number(s): "5475"

Test #25:

score: 0
Accepted
time: 242ms
memory: 88724kb

input:

1
500000 500000
>((>)(([(){}}[(({}]>>>(]{{<>[((}(><<><[}]>{}})><{<){>{>({}>}}<{{<]})([<])]}([><<><(]]><>){>}{]><(<{}<{)]{<<}]]<)({>}](<([)(>><[)<>]{){}<{>>{(}}<{(<)>(}{(}[]>><>)>[{>]([>}(}[}}}{]<>(<}))>][[<[(>{[([(})>][)(]}>)]<>}[<[>(}][{>[[([})])[]<{>[(<][[<)<{<{[<><<(]>)[[}{{<<](<>(]<(((<<]{>((])]...

output:

474

result:

ok 1 number(s): "474"

Test #26:

score: 0
Accepted
time: 259ms
memory: 88720kb

input:

1
500000 500000
{}][>>]]{}]}]]<(}](}]>][((][[[[[}}}<(<{)}]<(}]]([{({{]>(}({(}>)[<([>(>[<>}}[(}{>(({(})>{[[)}><{(>{{>)[{[((()])){}}{{<[]>(<[>]>]{)]]}[(]][}>><>[>]<)}>}]><}((<[><]{}[{(}]{}]][((()()})[(<{<)>[(<<}({}<[{)<>]}<][(>}<[]))][)>}<([}(<><(>>})]><[((<<]>>}]<>)<[)[[][[<>}[<<(][>}<>[[}{})>>(((<([...

output:

45

result:

ok 1 number(s): "45"

Test #27:

score: 0
Accepted
time: 246ms
memory: 88180kb

input:

1
500000 500000
{{)<]]>><>()))<>[<}<}{()())}({}<][<){[>(]){)[>>>)){>[}<}}(>}<]{[[[>[<{{>(<{({(}<(<>>(((>][)[]}(]){{)(({{}}({}]<]>}><<}>>(<(<))>]))<<[<)(]<)>(>{<>>[[{{[<<{]((>][)({[{>[[))<([><>>][}[<)]{}[(<>]<))<]>[>[>>>(}({>>)><)[{<[(}>}[()){{])>((}>}}>{>}>)>}(({((}}]{<([[)>[{<<}{)<)][})({{[>)>>>{)<...

output:

6

result:

ok 1 number(s): "6"

Test #28:

score: 0
Accepted
time: 268ms
memory: 103312kb

input:

1
500000 500000
{}[()]{}<>({}<[]>)[[{}]]<><><()>{{<<>>}{<>}}{}(<>)[]<[[]{}]><<{}>([[]<(<<><[[]]>{[{<<>(()){{{}[[{((){()((<>{(){<>}[{}()<()>[((()))]]}))})[[]]}<{}[((){}<>){[<[(<><><[<<[]>[]>]<[]>{<[<>]<()[]><{{}<<>[{{{{<>}<><<>{}>}}}{[]}]>}>>}<>>)]>]()}]{()<{}>}{}>[]()]]()[<>]{}}}{}()([]{})>}]<{}>{<>...

output:

142356

result:

ok 1 number(s): "142356"

Test #29:

score: 0
Accepted
time: 281ms
memory: 96188kb

input:

1
500000 500000
[{}]{}<>{}{}{}[][[{}[{(()[()])}]]()<()(<>{}[[()]])[<>][]>(<><{}[]>()[])]<[]<>>{[{}[][()]]}<>[{((){[{}[{<>}({[[]{}]([]<()<[]>{}><{[]}>{[][{}]})})()]<>]}<[]>)}(){}]<>()()(<>)()[(({}))<>]()()()<()[{}][][]>{}{}[{}]()()(){()[((<{}>())<()[[[]]{(()())(([][])(<>)<<>>)({})()}]>{}{()})]}(){[{<...

output:

38282

result:

ok 1 number(s): "38282"

Test #30:

score: 0
Accepted
time: 259ms
memory: 90460kb

input:

1
500000 500000
{}<>()()[]{}<>()[]{}((<[[(<>()<{{{[[{}]]}}}[<<[]>{(){<[<>]>}}>[]<{<({{{{}}}}[])>([]<<>>)<{}()(){}>{}<()>}>]<>>)]<<<>><>{}[([])]{{[({}[<([[[]{<()<><><{{}}[]({<><>}<><[()[()]][]>{}{})>[<[]>[]]>}([(<>())]){[]}<>[]]<{<<<>><[]<()>>[<[<[{([]{})<(())([(())]<>)[]<(){}>>}]>{}{}]>]<<>>>{}<>}()...

output:

4449

result:

ok 1 number(s): "4449"

Test #31:

score: 0
Accepted
time: 262ms
memory: 89168kb

input:

1
500000 500000
<>[]{<[[]]{{[]}}>}<[<>][]>[<{{}[[]]}>][][<>[{(<><>)}{}]]<<>(([]))><[()]<()>>[(<>[])]<>{()()[[][]]<{}>{[]}}[[{()<>(){{[]}[]}[<>]{[]()}()}[]]<>][]<>{}[]<>[{}]()<<[]<<{}>>{()}>><>{<({}[]<<>>)>([][(<{[[<><()><>[<><>([[<>([])]][{}<[([](())){}]()[]>{{}}])[]<>{{}}]]({{}}[]()()){{<>{[]}<>}}]...

output:

375

result:

ok 1 number(s): "375"

Test #32:

score: 0
Accepted
time: 250ms
memory: 88532kb

input:

1
500000 500000
[{}<>]{}{([{}])<{<{<{([[<([]<<><{[](()){[[[()][]]]}}[]{}>>{([][])}[{<>[]<[<>[]]>}])>{<(({})()){}{<><(<><[[{[<<>>]<>}[{<()<>[]>}]]<>{}()<{<>}[{}]{[{}][[()({{<<>>[(<>)]}})[]]]<>()}[[]<>][]>]>[][{}{}<>[<(){}[]>()]]<<({}[{<>[]{}<>{}}<{()}>]())>{}>){()}>(<>)}{[{}]{(<>)}[](()[()]<>)}>{[(<>...

output:

42

result:

ok 1 number(s): "42"

Test #33:

score: 0
Accepted
time: 251ms
memory: 102832kb

input:

1
500000 500000
(((()()(())(())()))()()())((()))()()(())(()((())()()))()()()(())(()()()(()))()(()())()()(())()()()(())()()()()(()(()()))(()())()(((()()))())()(((())(())())()(()))()()(())()((()()()()()(())(()((()))()((()(()))()))()))(()())()((()))()(()()(()(()())())((()((()((())()(()()))())(())())())...

output:

152712

result:

ok 1 number(s): "152712"

Test #34:

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

input:

1
500000 500000
(()())(((())((()())(((((())(((())))())((((()()(((())(()))()))(())))()(())()((())(((()()()()))(())))(((())()(((((((())(((())))(())((()()))(()()()))((()()(()())()))(()(()())()()((())))))()()))(((())(((()()(())))()(()())()((())()((((()()()(())(((()((())()()))))()((())(((()()(())(()((())...

output:

67010

result:

ok 1 number(s): "67010"

Test #35:

score: 0
Accepted
time: 228ms
memory: 90432kb

input:

1
500000 500000
(())(()(())((())(())))()(())()()()((()((()(()()((()))((((()))((())))(()()(((((()))(()(()))(()))(())))))))(())()(()())(((()((()()())())()()))((())()()(()(()(())()()))()()()()))()))(())()(())(((((()()())((()())())())()((()(())()((()))())(()(((((((()(())(()())((()()()()))()(((((()()))()...

output:

23151

result:

ok 1 number(s): "23151"

Test #36:

score: 0
Accepted
time: 256ms
memory: 89304kb

input:

1
500000 500000
()()((()))(())((((())(()()))((())()((())(()()))((((()((((())))())))(())())((())(())(()((((((())((())))(()())(((()))())((()(())()))))()(((((())(()())))())())(())()()((())))((()(()())()()(()(((()())())(((()()(()))()((())))())(()())()))()))))))())))(())(((((((())))((()()())())(())(((()(...

output:

7026

result:

ok 1 number(s): "7026"

Test #37:

score: 0
Accepted
time: 254ms
memory: 88196kb

input:

1
500000 500000
()()((()))(())()(())(((((()((((((())())))))))()(((()))))(((((())))(()(())((())())((()))))))())()(()()())(()(()(()(())())()(((()(())))()()()))(((())()()()()()))(()(((())(((()()())(()(())(()((()))(()))))()))))())()((()((())())))(((()((((()()()(((())()()((()()))))(()(())))(())(((()))))(...

output:

1762

result:

ok 1 number(s): "1762"

Test #38:

score: 0
Accepted
time: 276ms
memory: 117208kb

input:

1
500000 500000
{(([[{[((({[([({[({[<(([{[<[{(<{<<((<{{(<<[[{([{{<{{([{((({<<<[<<{{{<<([({[[{{({[{[{<[[<[<([{{[[[[{[[([{({([([{{{{<([<<{<{(<<[(({[([{[(<{[[[(([{[{{[[(({({{{{([{([[([<{[{[([{(<<<{(<<[{[({{(((([[[(({({<[[[{<(((<{((<<<[[<[<(([(([[({{<[[{[<{({[[{{<{[{[[<{<{([<{{((<((<(<<[<(<{{<<[<<({<([{...

output:

1

result:

ok 1 number(s): "1"

Test #39:

score: 0
Accepted
time: 260ms
memory: 117396kb

input:

1
500000 500000
(<[<({([[{<[[<<<[([<({<(<{{{(<<[{{<({([<{(({[{{(([{(({<<[<<(([[{{{<{(<(<[<((<<<{{({<<({<{[<<(({[{<<{((((((<(([([<([<[<[[{({<<[{[[{{{({{{[{{[[(([([((<(<({[([{{{{({((([<{<[(<[((<(([{<[((({{<<[[([<[<{[({<[[{({{{<<{{((([{[{<([<({[{<({((<<{<<(({{(<<<(((({{((<[[{[{[[[(<[{[[[([(<{{[[[<<(<{<...

output:

1

result:

ok 1 number(s): "1"

Test #40:

score: 0
Accepted
time: 278ms
memory: 117352kb

input:

1
500000 500000
<{<{<<<{<<<(<[<<[<[((<[{[([<[{{(([[[{{({([<<<[<[{<[<<(({{{<[{<([[{({(([[[({((<<[<{{<{<<(<<[[<<{[<[<{<({{<{<<[(<([{({[({<[{<<(([{[<<<<{<[[{<({<<(<[[<(<{{<<{<[(<{<<{<{<[{<[(((((<[{<{([[{[<[{<<{([[{{{{<{[[[{{<[(<[[<([[[<((<[<[(<[<{{<[((({{([{({{<<(<{{{(<{<{(<{(<[{{<(<[<({[([[{{[(({[[<<(...

output:

0

result:

ok 1 number(s): "0"

Test #41:

score: 0
Accepted
time: 278ms
memory: 117676kb

input:

1
500000 500000
{{(({<{<[[<((<<([<({[(<[{[(({({(<(([[(<[<{{({((<({[[{[[[<{<[<[((({{{[([<{[[([({[(<<<[[<([[({[[<(((({{((<{({{{({{{({[[[<{(([<((<<((([[<[<(<((({{<[(<{{<[(({({[{({{([<[[<<<(([<((<[(([[[<[{<([{(<<[<([{{{[<[({<[(<<{<[({<[(<[<[[<([[<[(<{<[[{[[{([{((<[{<([<(({[([{<({(<<((({(({{<{[[[<{{<{{([...

output:

0

result:

ok 1 number(s): "0"

Test #42:

score: 0
Accepted
time: 287ms
memory: 117728kb

input:

1
500000 500000
[<{<{<((<[<[{{({(<[<[(([<{[{<{(<(<[[[({{<([({(<[<[<[(<({(<{<<[{<<<[<{[{<[<[[{{((<{[{[[{<<<(((([[({<(<({<(([[({{{[<{<<<{<{{(({<{<{({({(({[[([<{[<<<<{{<{{<[(({((<[{[<[{<[{{<(<[{(<{[[<<(([<{<{[<({{<[<((<[[<<((<<(([<[<<{[({[[[<<<{[<[([([([(<[{{<{{[([<{{({{(([[{{[([(([{{([<{{[{{[[(<({<(({...

output:

0

result:

ok 1 number(s): "0"

Test #43:

score: 0
Accepted
time: 261ms
memory: 113824kb

input:

1
500000 500000
[<<<<{<{<({<{<<{({{[(([[[(({}<([<{{[[({<>({<{[[<{{[[[(<{[()]<<{[{}{{}<<(((<[([[[(<{[(({[<<<([([[<[{{{[]<><((<<({{((<([(((({}{[(<<[{{{<[[[({[[[{(<>[<><<([<{<[(({<<({[({{([{[({<{{{(((((({[{[{(({(((<{}({(<[[<{[<>]}[<(<[{[[((((({}<([<<<[([{[(<{<<[<>{(<<(<[({<({(<><[[<<<((<{((<<<([{<{}{({...

output:

162821

result:

ok 1 number(s): "162821"

Test #44:

score: 0
Accepted
time: 268ms
memory: 111840kb

input:

1
500000 500000
{}{{[{({{[<>[[]([<{({{{([<{[{<([{[]<<<{(({[<[{<[[<[<(<><({({{{[]}{[]([()][{<[[({()[{{((((([][<({}<([((<[({<(<>(<<<<(({({[[{{<<[[<<(){<[<(([({}<[{{{<[<<<()<<{[{({<{([<(<[]{{}{[[{{[<[[[(<><><{}{(<>)(({{[{<[(((<<<([{({<(({}<(<{[(<({(([{[<[<<[[[[<<>()<<<((<[(({<<[<[[<<{[{{<{[[][[[[{{{}{<...

output:

16576

result:

ok 1 number(s): "16576"

Test #45:

score: 0
Accepted
time: 275ms
memory: 113160kb

input:

1
500000 500000
{([((([<>[{[((((<({{({[([{[]{<[{[([{[<<<{({([[][[(({[[<([{([{<{([{(<(<(<>{[[(({<({[]<[<>[<{<(<([<{(<[()<[{<<[((([[({[[<{(<{{[{{{{[((<<>[[<<{}((<({(({(([{({{{<[<><{<({[{{({[]{([<{<[{<<((<[[{{[({{[{(<{<[{({{[[<([{{[{({([<><((<{(([<<[(<<(<(<[[[<{[([<{}{({(<{{{{[[<<[[(){}<[({<><([()[[(<(...

output:

1262

result:

ok 1 number(s): "1262"

Test #46:

score: 0
Accepted
time: 277ms
memory: 114228kb

input:

1
500000 500000
{(([[{{}{<{()[]([<<<>{[(([]({}<[((<{[]<[[]<({[((<[[[{[{(({([{([<[({[<<<[<<{(()[<{[{(<[[[[][](<(<{<{()()[{}{}<<{}<(([[{[<[((<[[<{(({([{(<>{<[[{({[{}[[[{<[{{{(){<[[[<{}((((<(<([<(<((<[<<{[[{{{[[<{{[{}<>({{({[[<(<{{(<<{{{[()()[[()]<{<({[(([[[({[]<{[[{<[([()((([]([[[((<<[<(()[]{{<<<({{[(...

output:

340

result:

ok 1 number(s): "340"

Test #47:

score: 0
Accepted
time: 295ms
memory: 114072kb

input:

1
500000 500000
[[]<<<[(()(<()(<<(<[({{[{[{[(<{[[][<{([[({<<{<[[]{{<[{{}((<({<{}[{<()>{[<{((<[{<({[{{({{<{[([[(({}({{()[<{{[{}((({<<><{}[[(<[[{{({}<{<[[]{{[{{([({{<{{{[(([<>{{[[(([[(<[[[<{(<<[[({<<<>(({([{([<[({[<<<><[({<{[<{[{(<[[[[[{(<(<{<{(({}{{{}<<>(<(([[{[<[((){[({({({([[]<<{{[[<{[<{[[[{<><<{<(...

output:

100

result:

ok 1 number(s): "100"

Test #48:

score: 0
Accepted
time: 245ms
memory: 114764kb

input:

1
500000 500000
(((((((((())())((()((()()((((()((()(()((()((((((((((((((((((((((((((((((())(()(((((((((()((((((((((((((((((((((((())((((((((((((((((((((((((((((((((((((((((((((()((((((((((()((()((((((((((((()(((((())((((()((((((((((()(((()((((((()((()(()((((((((((((((((((((((((((((((()()((((()((((((...

output:

224975

result:

ok 1 number(s): "224975"

Test #49:

score: 0
Accepted
time: 250ms
memory: 115440kb

input:

1
500000 500000
((((((((((((()(((((((((((((((((((()()()((((()((((((((((((((((((()(((((((((((((((((((((((((((())(((((((()))(()()((((((((((((((()(((((((((((((((((((((((((()(((((()(((((((((()(()((((((((()(((((()((()((((((((((()((((((((((((((((((())((((()((((((((((((((((((((((((((((((()(((())(((((((((((...

output:

220198

result:

ok 1 number(s): "220198"

Test #50:

score: 0
Accepted
time: 260ms
memory: 115416kb

input:

1
500000 500000
((((((((()()(((((((((((((((((()(((((()((((((((((((((((((((((((((((((((((((()((((((((((((((((((((((((((()((((((((((((()())(((((((((((((((((()((((((((((((()(((((((((((((((((()(((()(((((((()((((((((()((((((((()(((((((((((((()((((((((((((((((((((((((((((((((()(((()((((((((()(((((((((((((...

output:

214328

result:

ok 1 number(s): "214328"

Test #51:

score: 0
Accepted
time: 275ms
memory: 115176kb

input:

1
500000 500000
(((((((((((((((((()(((((((((((((((((((((((((((((((()(((((((((((((((()((((((()(((((((((()(((((((((((((((((((((((()(((((((((((((((()((((()(((((((((((((((((((()((())(((((((()()((((((((()()(((((((((((()(()((()()((((((()()((((((((((((((()(((((((((((((()((((()()((((((((((((((((((((()((((((...

output:

198470

result:

ok 1 number(s): "198470"

Test #52:

score: 0
Accepted
time: 276ms
memory: 113296kb

input:

1
500000 500000
(((((((((((((((((((((((()((((((((((((((((((((((((((()(((((((()(((((((((((((((((((()((()((((((((((((()((((((())(()(((()((((((((((((((((((((((((((((()()((((()((((()((((((()((((())((((((((((()((((()((((()(((((((((((()(((((((((((()(((((((((())((((((((((((((((((((((((((((()(((((((()((((((...

output:

144248

result:

ok 1 number(s): "144248"

Test #53:

score: 0
Accepted
time: 130ms
memory: 93148kb

input:

1
500000 500000
()[](){}{{}[[]][]}[<>{{[[<>([{}]){<>}<[]><()>()]]}({}([](){}{{()}}))}][]<>{{<[]>}}<[[]]{}>[]{}<>([]){<>}{(())[]}()[<>]()<>()<<>>()({}){}{[][{<{(<>[[[(([()]{<{<>}><>}(<>))<{(<<>>{})}>{()}[])]{}]<<<{({}){{}}}[]>>{}{}>][]())()<()>}<>>}(){(<>){([](())<><((){}<{{}}>({(<>{<<[{}[][]]>[]<[]{...

output:

108

result:

ok 1 number(s): "108"

Test #54:

score: 0
Accepted
time: 115ms
memory: 93204kb

input:

1
500000 500000
<[(<>)]()({{}{(){[<[[]]>]}{{}{}()<>}<>}}(<[{<>{}{[]}{}{{{{[<[][]>]<>}({[]{{}}[<[[[]({})({}){}[{}]()]]<{}<{[][]<>}>>{[{}](){}}>]}({})[[{<>}[]()]](<<>[]>))}}}()}((([]([]))<{{}({})}[][]{}>[]{<>})<><>[])]>[]){}({}))>{[]}<>[][]{{}(())}<<><{{}[]{}}<><()<()>>>()>[<><{}>]<>[(){}]<>{}<{}>{{}}...

output:

40

result:

ok 1 number(s): "40"

Test #55:

score: 0
Accepted
time: 108ms
memory: 93296kb

input:

1
500000 500000
{()}<><<><{[]}<>>[](([[{<>}{}][[]]]{}{})[(<<>>)][])<[][]><[[]{}][[{}]]>>{{}}[<>][]{[]}(){{}}<>{}[(<>)]<{()}<{[[{{[]<>}[<>]}{<<>>}]{}{{[](<>{}{}[{}])}{}{}[[]][{{}[]}][([([]())<>])()<>]{}}[]]([]<{{}}{{}}>[]{})([])}>><{}<>(((){}[]))([])>()([]{()[<{}>]}<>)<()>(([]))(<<(()){}>({}{}<([<>])...

output:

53

result:

ok 1 number(s): "53"

Test #56:

score: 0
Accepted
time: 118ms
memory: 92992kb

input:

1
500000 500000
{}(<[][]><[]<>>[]){[(()[[{}]()[]]<>((())))](()((){()([{<>}][]{()}())[{}()]<{[]}><>[[<[][<>()[{}]]>[()]{}]{[()]}]}<><>(){(({()<>[<(([]{}[]){<[{[]{{<<{[{<><(){[]{<>}[[]]<{[]<<()>><>{[<{<>}[<{}<>><[]>]()>{}]<>{}[[]][]}}>}>}]{}{()}<{}<()()>(<>)<>()()>[]}<>{[<>]<<><[<>()<[][]{}()>]><{<[]>...

output:

28

result:

ok 1 number(s): "28"

Test #57:

score: 0
Accepted
time: 112ms
memory: 93168kb

input:

1
500000 500000
[]<{<[[]{[]<>([]){}}<<{()(<>)}>>]>}<[]>>{<>}(([]())<{}([]){}>((<>)[]){})<[()]({{[]}<{[{[<{}>]}]}{()}{{}}>}<>[[]({})()])>{}()[<>]<(<[]>{([])}()[])>[{([])()}]<[{}]{[](<[[<>{<()><<<>{}{}>>}]](){}>)<>}{}{()<()>[][{}][{[]<()[]{}>}()](){[[]]<<>[]({})()>(<>)}}[[<[<{}<>><<([[[({{}{{}}[(<>[[(...

output:

27

result:

ok 1 number(s): "27"

Test #58:

score: 0
Accepted
time: 122ms
memory: 93080kb

input:

1
500000 500000
{{}}()<>()[][[]]{(({}[[[[]][{(<>)[<>((((<<{{}(<>)[]({[()]}()<>)[]}><>[][]{}[[(<([])>())](({}{})<([])>[[]]{<<{(()()())<[](<>)[]>}>>}<><[(<>[])({({<{}{{(<{[]({})}[]>)}}()[]>(()<><[<(()()[()])>](()<><([]<>)<>{()}{{}}()>()){{{([(){[]}{}<()[{[]}{}]<>{}>{}]){}}}}[<><>]><{<>([{{<>{}}<<>>[]}...

output:

146

result:

ok 1 number(s): "146"

Test #59:

score: 0
Accepted
time: 112ms
memory: 93312kb

input:

1
500000 500000
[[]{{}([])[]}<>()][]{(){}[]<>}{<>{}}{<>([])[[][[[{{{}{<<>{}<[]<>()>>}<>}([]()[{()()(<>)<{}>}[]])}]<<<>>[{}()<([])()>{}]>][]]([[[]<>[()([]()<<<>[]>>())]([])]])](()[][])[]}<{}>()<[<>]{}<>><><({()}{<><({{[<><>]<{(<>())}>}<[<>{()}(){}][]{(<>)}()[([<<[{}][]{}>>])(<><><>{<>})]>}[[]{}])[[][...

output:

133

result:

ok 1 number(s): "133"

Test #60:

score: 0
Accepted
time: 115ms
memory: 93340kb

input:

1
500000 500000
<[][]><><>({}([()]{[[][(){<{}[]><[((<>)[({}{{}})])[<<<>{<><>}>((<<>>)(<>{()(<>)()(){{}}<>(<<<<()>>()>>)<>})){}{}<[{}]>>{}[]]]{[([](<{}{[][]()}<{{[([]{<()>[<>[]{}][]})<{()}>]}{[][[[][[](()[][])<<>{{}}[]([[<>]])[()]>][]]][]}[]()(<>)<>}>{<<{<<>><>([]){{}[{}]}(<<<<>>>([<>[{{(<>{}[]{}<>{}...

output:

38

result:

ok 1 number(s): "38"

Test #61:

score: 0
Accepted
time: 113ms
memory: 93260kb

input:

1
500000 500000
{}((<{([()]<>)({{<([{<[[<[]{({})}>{{}<>}()]<({}){<<><>[]>[{({[][][](<>)})<>[{{}{[](())}<{()(([][[{[[()]]([{{}(<>[][{<<>>}])[]}]()(<>))}][<({{}[]}[[[]]<>])()({})[[[]<>({[]{<{<>}(<>)>{{([(<{}<>>)<[<()[[<[]>]((<>))([[]](){{()<><>}{([{}(<{}>)])[{<[]>[]}]}}{}){}[]]>]><([[]])>[](())[()]]()...

output:

45

result:

ok 1 number(s): "45"

Test #62:

score: 0
Accepted
time: 110ms
memory: 93136kb

input:

1
500000 500000
[[(){[{[]}]}<>([](())(<<(<()[{}()]>[(<([[]()])>)<<<>{}{([])}>><<>()<>{}>][])>>){})[<><[]<>[(<><{}>[<>[]])[[()]]]({})>]]()]{}({}){}<[][()]>(<{()}>)(<>)<()><(<<<><><>>()>)>()<>()<{}>[]{}()[]({}){{<>{}[]}{[]}}[<>][]({}{})<>[[]<>()]<[<>{[]({{}<[[]()]{}>})({}<>(<>[()]{}(<>))())<(){(){{{}[...

output:

128

result:

ok 1 number(s): "128"

Test #63:

score: 0
Accepted
time: 110ms
memory: 80956kb

input:

1
500000 500000
<><><>{}(){}[[[]]][[[[{}]]{}<{[](([]{<>{}}))}>]<[({<><>[]}[])[(())]](){[]()<>[]{({{}})}}()[()<>{{}{([()])}}]>]({{[((<(<>)>[(<[]>)[]]){}{}()<<>()><([]<[[]{<{}>}]{}[]>([[]()]){}<[<{<({(()({}<{}>{[]([[]]{}([()({}[(){}{}[[]]<>[](<[[]][](([]<>{[[]]}())(<>)(<{}()>[]))[[{[()]{}}[<>()[][{[{}...

output:

32

result:

ok 1 number(s): "32"

Test #64:

score: 0
Accepted
time: 112ms
memory: 80916kb

input:

1
500000 500000
{{<<{}[]{([<>][]{}()(){})()}>()>}}(){(<>[])}(){}[{(()[]{})()(<>[]<<>>)<>}]{[<{{}[]}>{[[<<<[[(<>[]){}]][[[[[]{}<<<>{<><>[]}([({})]{{()}})>><>]]<<>>]]>{{<>(){}[()]<>[]}}>{<><<>><<>>}>]]<>[](<>[()][])}]}{}{()<>}{[][][]{{{}{}}[(([]))[()[[](((){}[{()}][[][([])(()())([{(()[([][]())<>])}{<<...

output:

15

result:

ok 1 number(s): "15"

Test #65:

score: 0
Accepted
time: 102ms
memory: 80884kb

input:

1
500000 500000
[{}]<>{<{<><<>>}>}{{<({})>}}{()}(((<>)))<>{}()[]()(<{()}>)(({{{{{}{}{{}(){}()}[]<{}>{<>}}}[{}]{<>()}}}(<<(({{}}))>>))){{([<>({{{}}}[]{}[])[[[{{}()<{[]<><()<>>[]}>}(<{<{{}(<>){{()}<>{}}()}>}[[][{{()}}[]]<>{}<>]>)][[<>]]]]{[](<>)<[[[[[<[]>]]]]]<[(()[])]>><>}])(<><[]{}>({}({}[({{}[{()()...

output:

9

result:

ok 1 number(s): "9"

Test #66:

score: 0
Accepted
time: 97ms
memory: 80788kb

input:

1
500000 500000
()[{[<>]<{<>}[[<[](){}>]<>([])]>{(<{}{<{[]}[]>}>)}}()]<<>><>{}()<<(([<><{[]}>{}{{}{}<>([][]({}){}<>())(<><<>>)<(()){()}>}]{}<>{}<>))[[]]{[](<{}((){[]})>())}>>[][]()<[](<({(()[{}<>][<<>>])({})})>{{<>}{}{}})><><>{{}[]<{}>{}()[{<>}]}[][]<[[][()]]{}>()<[<>[<>[<>]]]>[]()(){}[]<<>>{[[[]{}<...

output:

6

result:

ok 1 number(s): "6"

Test #67:

score: 0
Accepted
time: 103ms
memory: 80852kb

input:

1
500000 500000
<>([<><>][<<>()><<()>>])(())<[]><>(<>){}(())[]()<{[]}>[({})[(<<((<>[])<[]>)([[]])>()((<>{[]()()<()>})()()<<>><(()<>)><{<{<>{}}[]>}{}[]>())<>>{<>[(())(())]<>()}{<>})]][()[]{{{}()<>}}{<>}]{}{<>({}<[()]>)[]}[{}]{{<>}}{[[{{}}()]{()()[{<[]>}{{{}[<>]}}<{}><<>>()()[(<><>[])]]()[]}][({}<{}>)...

output:

4

result:

ok 1 number(s): "4"

Test #68:

score: 0
Accepted
time: 102ms
memory: 80768kb

input:

1
500000 500000
(<>()){}[]()<[[]]<<[]>>>[]{<>}({(){()[<{(<[([[]<>])]<>>[[[]{{{}}}]])}<[]>>]{[()<>]([{[(<<>>)]{}}{[]({})}{()}])}}})(<>)<>{[[]][]{}}<<<>{}>>(<>{})(<<(){}<><>>>)<>[]{}{}(()){{}[][[][()]<>]()}[{}(<>)][[][]]{}<()()[{()}][()](())<>>{<>}<()><><>([]{})<>[]<>[[(())<[]<({})>>][[]<()[]{}<>><{}>...

output:

7

result:

ok 1 number(s): "7"

Test #69:

score: 0
Accepted
time: 100ms
memory: 80760kb

input:

1
500000 500000
(<>){}(){}<<>([])>[]<<[]<<>>>>(){<([]())({<<>(){}<{}[()([{}]({}<>([][]){()})<{}{}[]>)]>[]>}{})>[[{}[<>[]][{}][]]]}{<>}{}<[]>{{}({})}{{<><>[[<>]](<[]>)()}}()<{()(){{}({})}}>()(()<>[])[]{}()<>{[]([[[{()(((([()]<([()]){([][]<({}[{}])><[<>{[()]}<<>>[<>]{}]>()){}{<>}}>))))}()<>]<>][()(){[...

output:

5

result:

ok 1 number(s): "5"

Test #70:

score: 0
Accepted
time: 97ms
memory: 80884kb

input:

1
500000 500000
[{<<>{()}{}>}](){}<[]>[{[<>]({<>}){}<>}]<({<>}{})>[<()>(<>{[<<[]([{}][[[]()()]])>>{}()]}[])()({}[{}]<><()><(<>[{}<>()]){}>{}(<<>>[[]<>{()}{}]{[]}))<<[<[()[]][[{<<<{(()(())<{[]<<{({(<{{[]{{}({})}<{{()[]()}}>[]()}}{}>)}<[({{}})][]{}{}>{})<{[{}(<([[]{}])><{}>)<>]}>[{()}]}>><>{<(){}>()[<...

output:

2

result:

ok 1 number(s): "2"

Test #71:

score: 0
Accepted
time: 100ms
memory: 80772kb

input:

1
500000 500000
()[<(<[[]]><>{<()[][]>[]}<(({}[])[[[]]][(<>{})])[[]]<>{[]}>)>][][][][(((<[]>)))][()]<>[[()]{{[<>][[[]](<{[]}{}{}><[]>){[(<{}(()<[{}]()<><<>><<>{[]<([])>}>{<[{}]><>}[(([[({}[][]{}{[<>]((({{}})))<>})[]]][<<()><>(())>]({}{})))<(<>())[{}]()[[]{{{<<(())({}()())<{{<<{{}[()]((((({})[](<()()...

output:

1

result:

ok 1 number(s): "1"

Test #72:

score: 0
Accepted
time: 106ms
memory: 80732kb

input:

1
500000 500000
<>{<{{<{}{}()<{([]{<>})}>[(<><>)]>(){}[][]}}<>>{}<>}<[{{<>}}{<[<><>[[]]]{[<{}[[<>{}][([])]<>]>][[]]}>}(()){}]><[]>[(<(<><>)>[[]])[]()]{}({}[[[]({[<>]}{{}<>})<<>>]])<>([](({<>({})}))([[]][]))[[{[<{}>]<()[[][][]]()<<><>>>[]<>}]()]<()()[]>[]<>[{({}{})<>}]<{}({})>{}<[]{}[<><>()[]][]>(())...

output:

3

result:

ok 1 number(s): "3"

Test #73:

score: 0
Accepted
time: 116ms
memory: 93116kb

input:

1
500000 500000
[][]{{[]}[{{()}(<{({<><>}[])[]{[<>]}}[[<{(<<{[]}{[]()}>{{[(<>)<[]>]{}[{}({{{}}}<(()[]<{}>){<<[]>[{({}){}}<()()>{}<>[]]>}([{()<[<>]>[]}]){}{}>())(<>)]}}{<<>>([]{{({}<{}>)[]}}<{}<>()[<()()>{}<[][{<[]{}{[]()()<<{[()<<<>{{[[(<()<{[<{}[]<{<{()}[]<<([[]][]()<>)>{<>{}}><>[()]{{}}>}>>[]<>]{[...

output:

42

result:

ok 1 number(s): "42"

Test #74:

score: 0
Accepted
time: 116ms
memory: 93112kb

input:

1
500000 500000
<(<({{}()}[]{})>()()<<[]><>(<>){{}}()()>())><<{{{}}}{}>><><[[[]][{{<>[]}{}[{[]}]<[][{[]<>({}[<(<>[])>{{{()}<[]>[]{}}([()[<(<()({}(([])[{<<[]{[]}>{{<>[(){([]{()})}][<>]}}>()}]{}))()>[[][]])>[][]{()}]{}[](){()}[[]](){}[[([])]<{}>]]<()>[]<>){}}])({<[[]<(){}<{}[][]>{}>[([<>]<<>{<><()<<{(...

output:

157

result:

ok 1 number(s): "157"

Test #75:

score: 0
Accepted
time: 108ms
memory: 93140kb

input:

1
500000 500000
()()<>{}<>{}<>(){(<>)<>()}<{()((<{}([<((){}{<>(<><><()(())()[]><>)}<>()[(){}{}]()){}({})><<[]>>][]<><{<(<({})[]>)>[(<>){<>{(())[([<(){}()>[]]{}<[((){[()]()}{{[]}})]()()>([{<[{()}]{[]}()><>{}}][]{({{<[]>[[]<>[{[]<>}{}][]]{{}[]}<[[]([])]><>}{[][<>][{{<()>}}<>](()())<>}[{}]}{([]())})({[...

output:

164

result:

ok 1 number(s): "164"

Test #76:

score: 0
Accepted
time: 103ms
memory: 93104kb

input:

1
500000 500000
([]<>){}<[]>{}[[([]{})({[]()}<>)<[][]{{[<><([]<><[]{}>[{{({})}}])[[()[]]]([{[([])<>{}]}(<<>([]<>)>[]((())[()<[<>[]]<(<>{})<>[()<>]>>](())[()]({({})[[][][]][[[]]<>[[<>{}<>[]<>]]][]()([{}()[]]){<>{{}{}({})<>}}[](){{()}}{[]}}(<>){}{{}}((){}<<>()>)<>))<>)]<>)>[[<>][]([])()([<<>[<>]>]){}[...

output:

46

result:

ok 1 number(s): "46"

Test #77:

score: 0
Accepted
time: 120ms
memory: 93164kb

input:

1
500000 500000
{<((<(<>{}[][[]]<>({(())}{}<><<>>){}<<<>>>){{([<>][])}}{{(())()([])}<<>><[[({})<>]]>}<<>[]{}[()]{}{<{[]}([])>}{<>}<{}<({[<<>({})(<<>>()<>)>]{}}{}{}[{{}()<{}>}()[]{(<>)[]}])>>([<>[][]]())()[[]](<>)((<>)())<>>{(<>)()}>{{({(<>)}){<{<>([(())]({[]})<>)}((<>))>{}}{[(){}[]{<>[][]}]()}<[[<>]...

output:

160

result:

ok 1 number(s): "160"

Test #78:

score: 0
Accepted
time: 110ms
memory: 80772kb

input:

1
500000 500000
<>{<{{}<()[]()[][]><>}>}{[]}(){[]}()([()({})])([]<{}{}>)<>()(){[]()<>()<>}<<>>{}({(<><(<>)>)<{}[]>})((){[]()}){}<{{[()]}<[(<>)]>}([{{}<<{(<{()<>}><<>[](<()<><[][(){}<>]<()><[]()[<([()])<>>()[]<<>>{}<>[]<<><()>><()<>[(<([])(()[])>)]>]>()<{}><{(){}([]<()>)[]}<[]()<>>[]([]{<{}>}[])>>>)(...

output:

3

result:

ok 1 number(s): "3"

Test #79:

score: 0
Accepted
time: 97ms
memory: 80820kb

input:

1
500000 500000
{()}<<<[<>[]<>]{([<{}>])}>>>{<>}[](<>{(<()>)[([{{}}<>]()[[][<>]]){}<>][{}{}()[{}[<>]][(){(<>{})}][]]}[<>{[[<>]{[]<[({[]})]<><{<()<{}>>}[]>>}]}][])<>()()()[]{()()}[](){[]()[{(){}}]<(()(){{}})>}(([([]<><(()()<[]>{<{{}}>}()<<()>>)>)]<<<>><<({()})(<{}<>>[]<<>><{{(<>)}}>){}>>>()<<>[{<>([<...

output:

6

result:

ok 1 number(s): "6"

Test #80:

score: 0
Accepted
time: 97ms
memory: 80772kb

input:

1
500000 500000
<>(())()[<>{{}}<>(())[(([])<<>>()[]){(<>)<[]([])>}]{()<{}>[]()<[<>]>}{}]()({}[](())<[<>](){[[<>]][[[]<><({{}(){<()>}[()(<[()<([[(([]([][]<>)){})([]<<>[][{}]{}>(<><>))][()[{(<{}>)<>}]]{<[]>}{{}[]}<><{(([])[[(<>())<>(<[[]<>{{()[[](<[][<([[<>()([({<{}>([{<()><>}<><>{}<<(<{}(({{{}<>}{}}<...

output:

5

result:

ok 1 number(s): "5"

Test #81:

score: 0
Accepted
time: 103ms
memory: 80928kb

input:

1
500000 500000
<{()}><[][[]]>[]{}([]){}{}(){()(){()<>()(([[]{{[]{[]{}()}}}{<[{}][<[[]{[]<[]>}]{{{}<[<>[]]()><{}[{}[[]](<>[({})<<>>{{}()<>}])[][()[]{([[]])}]{}][<[]>]>{}<({}[(<[][<<()><>{<>{([]){[]{({[]}[]<((())){}>[{}])<>[<>[<[]()({}<>)(<>()((){}))()[]>{}]]}}}}[][]>]>)])>}}>]<>>[<[]><>[<>]<{<>}[[<[...

output:

6

result:

ok 1 number(s): "6"

Test #82:

score: 0
Accepted
time: 88ms
memory: 80832kb

input:

1
500000 500000
{[]}[]<>[]{[{[]}[<>(){}[<[[]({(<(({<><>{}}(((([][(){()}])())())){}))>)}[])]>{}<>[<>{}]]]]}[]((){}){[<>(<{}(<([<>(({<[[[]{}]]>}))][][])>)[(<>{(<>{})<[<>]>}[[()<([]())>()]()])<<>[<[[][]]>[]]>]>()(((<><(()){}<<>>[]>)<>{{<><>}}{<()[]()>([((()[{{}[()]}<>]))()<[{}]<{{}}>{}([[]()()])>][]<<>...

output:

4

result:

ok 1 number(s): "4"

Test #83:

score: 0
Accepted
time: 115ms
memory: 93224kb

input:

1
500000 500000
<[()[]()[{}]{}]>()[{}{[[(){{}}]]<><>[]}]{<>{{}{<({<([])>}{(){{[]}}{<>(())}})>}}<()>{}}<>{<()>}<>{{()<>}{{()[][({<[<{{}<>{()<(<<>{{<{}>}}>{{{}}}<>)>{[]<>}{}}}>{}{<>[](<[]>())}]<>>[()()]})]}<{({})(<><>)}>}{(([]{}))}{}()}()()(<<>[]>{{}})([(([<[]<[]>{}<>[]><>]))[]])[]<>{}<>(<<<<<{}<>[]>>...

output:

120

result:

ok 1 number(s): "120"

Test #84:

score: 0
Accepted
time: 110ms
memory: 80744kb

input:

1
500000 500000
(){[]}<>[<<>()>][[()]{<<>[{[[][<<>>](<([[]{{}}((()<<({{}({}{{[]({}([])<(){}[{}]<{{{}}}>>)}})}<<>>)[()<{{}()[]}(<[<{[][][<[[<>]<>]>[<>]([<[]>[{}<>][(()[[]<(((([])[][[]()])))(<>)>])]])[]]}>]>{})>({}[()])()]<>{}>>{}<[]>()))(){}{<>()}])>[()]([]<<[]<()({()})>><>{}{}()(<>{{}})>[]{{}}{<<>>[...

output:

3

result:

ok 1 number(s): "3"

Extra Test:

score: 0
Extra Test Passed