QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#615294#6822. Bracket QueryCMingWA 544ms21108kbC++171.9kb2024-10-05 18:00:312024-10-05 18:02:29

Judging History

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

  • [2024-10-05 18:02:29]
  • 评测
  • 测评结果:WA
  • 用时:544ms
  • 内存:21108kb
  • [2024-10-05 18:00:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int  N = 3005, M = 15e5 + 2 * N;
int h[N], e[M], ne[M], w[M], idx;
 
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
 
int dist[N], cnt[N];
bool st[N];
int n;
bool spfa()
{
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    queue<int> q;
    q.push(0);
    st[0] = true;
int count = 0;
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] < dist[t] + w[i])
            {
if(++count > 20*n)return false;
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n + 1) return false;
                if(!st[j]) q.push(j), st[j] = true;
            }
        }
    }
    return true;
}
 
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    memset(h, -1 ,sizeof h);
    int q; cin >> n >> q;
    bool flag = true;
    while(q--)
    {
        int l, r, c;
        l = 1, r = 1, c = 1;
        cin >> l >> r >> c;
        int len = r - l + 1;
        if(c > len) flag = false;
        if((c + len) & 1) flag = false;
        int p = (c + len) / 2;
        add(r, l - 1, -p);
        add(l - 1, r, p);
    }
    if(flag == false)
    {
        cout << "?";
        return 0;
    }
    for(int i = 0; i < n; i++)
    {
        add(i + 1, i, -1);
        add(i, i + 1, 0);
    }
    for(int i = 1; i <= n; i++)
        add(0, i, (i + 1) / 2);
    add(n, 0, - n / 2);
    add(0, n, n / 2);
    if(!spfa()) cout << "?";
    else
    {
        cout << "! (";
        for(int i = 2; i <= n; i++) {
//            cout << dist[i] << " ";
            if (dist[i] == dist[i - 1])
                cout << ')';
            else
                cout << '(';
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7716kb

input:

4 1
1 2 0

output:

! ()()

result:

ok ok

Test #2:

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

input:

4 1
1 2 2

output:

! (())

result:

ok ok

Test #3:

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

input:

2 2
1 1 1
2 2 -1

output:

! ()

result:

ok ok

Test #4:

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

input:

2 1
1 1 2

output:

?

result:

ok ok

Test #5:

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

input:

4 0

output:

! ()()

result:

ok ok

Test #6:

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

input:

8 2
1 5 1
3 7 1

output:

! ()()()()

result:

ok ok

Test #7:

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

input:

3000 0

output:

! ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()...

result:

ok ok

Test #8:

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

input:

2 1
1 2 2

output:

?

result:

ok ok

Test #9:

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

input:

3000 1
1 3000 0

output:

! ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()...

result:

ok ok

Test #10:

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

input:

8 2
1 6 2
3 7 1

output:

! ()()(())

result:

ok ok

Test #11:

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

input:

3000 3
1111 1113 3
1112 1114 -1
1113 1115 3

output:

?

result:

ok ok

Test #12:

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

input:

2 1
1 2 -2

output:

?

result:

ok ok

Test #13:

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

input:

114 13
3 98 14
5 100 10
7 102 6
12 107 -4
11 106 -2
14 109 -8
6 101 8
10 105 0
19 114 -18
1 96 18
9 104 2
16 111 -12
18 113 -16

output:

! (((((((((((((((((())))))))))))))))))()()()()()()()()()()()()()()()()()()()()()(((((((((((((((((())))))))))))))))))

result:

ok ok

Test #14:

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

input:

114 7
3 109 -1
5 111 -1
6 112 1
8 114 1
2 108 1
1 107 1
4 110 1

output:

?

result:

ok ok

Test #15:

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

input:

114 68
5 17 -1
15 27 -1
74 86 1
67 79 -1
97 109 -1
72 84 1
51 63 -1
82 94 1
22 34 1
61 73 -1
83 95 -1
32 44 1
76 88 1
11 23 -1
94 106 1
65 77 -1
70 82 1
38 50 1
17 29 -1
29 41 -1
27 39 -1
48 60 1
59 71 -1
13 25 -1
60 72 1
53 65 -1
21 33 -1
36 48 1
14 26 1
46 58 1
42 54 1
28 40 1
1 13 1
55 67 -1
3 15...

output:

! (()())()(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())(()()())()(()()()()()()()()()())()(()()()())

result:

ok ok

Test #16:

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

input:

114 68
32 42 3
102 112 -1
58 68 -3
3 13 5
9 19 -1
84 94 1
47 57 -1
67 77 -5
75 85 1
43 53 -1
68 78 -3
93 103 1
89 99 -1
73 83 -3
80 90 -1
97 107 1
65 75 -3
19 29 -1
12 22 -1
17 27 1
51 61 -5
78 88 1
14 24 1
33 43 5
50 60 -3
61 71 1
46 56 -3
103 113 -1
100 110 -1
28 38 1
36 46 3
54 64 -3
37 47 1
60 7...

output:

! ((((()((()()()))(())(((())))()()(()()((()(()()))(()()))(()))))(((())(())))))((()))((())()()()())(()()(()))()()()()

result:

ok ok

Test #17:

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

input:

114 50
61 96 -2
25 60 4
22 57 4
57 92 0
4 39 6
36 71 -4
18 53 6
45 80 -2
52 87 -2
37 72 -4
30 65 -2
13 48 8
69 104 2
2 37 6
47 82 -2
23 58 6
73 108 2
8 43 4
11 46 6
7 42 6
12 47 6
16 51 8
64 99 0
6 41 6
63 98 0
14 49 8
66 101 2
78 113 -4
75 110 0
49 84 -2
42 77 -2
39 74 -2
44 79 -2
54 89 -2
67 102 2...

output:

! (())()()()()()()()()()(((())((()(((())()()))((((()()))))(()()))))(((())()((())))(((()(())))(()())())(((())(())))))

result:

ok ok

Test #18:

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

input:

114 56
50 107 -42
30 87 -2
18 75 22
25 82 8
38 95 -18
37 94 -16
19 76 20
31 88 -4
48 105 -38
26 83 6
47 104 -36
14 71 30
10 67 38
3 60 52
43 100 -28
42 99 -26
9 66 40
22 79 14
8 65 42
29 86 0
23 80 12
34 91 -10
12 69 34
16 73 26
40 97 -22
36 93 -14
33 90 -8
49 106 -40
1 58 56
55 112 -52
46 103 -34
3...

output:

! ((((((((((((((((((((((((((((((((((((((((((((((((((((((()(())))))))))))))))))))))))))))))))))))))))))))))))))))))))

result:

ok ok

Test #19:

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

input:

114 56
1 58 2
33 90 0
22 79 0
54 111 0
46 103 0
24 81 0
31 88 0
19 76 0
45 102 0
14 71 0
55 112 0
17 74 0
20 77 0
4 61 0
56 113 0
43 100 0
48 105 0
2 59 0
34 91 0
5 62 0
6 63 0
32 89 0
52 109 0
49 106 0
11 68 0
38 95 0
28 85 0
27 84 0
39 96 0
35 92 0
16 73 0
21 78 0
29 86 0
47 104 0
8 65 0
15 72 0
3...

output:

! ()()()()()()()()()()()()()()()()()()()()()()()()()()()()(())()()()()()()()()()()()()()()()()()()()()()()()()()()()

result:

ok ok

Test #20:

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

input:

114 56
36 93 0
55 112 0
48 105 0
26 83 0
19 76 0
25 82 0
34 91 0
46 103 0
3 60 0
14 71 0
2 59 0
18 75 0
33 90 0
23 80 0
54 111 0
22 79 0
41 98 0
15 72 0
30 87 0
56 113 0
29 86 0
4 61 0
24 81 0
12 69 0
43 100 0
20 77 0
7 64 0
21 78 0
38 95 0
6 63 0
51 108 0
32 89 0
39 96 0
10 67 0
8 65 0
35 92 0
16 7...

output:

! ()()()()()()()()()()()()()()()()()()()()()()()()()()()()(())()()()()()()()()()()()()()()()()()()()()()()()()()()()

result:

ok ok

Test #21:

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

input:

114 56
3 60 0
27 84 -2
29 86 -4
9 66 -4
17 74 -8
7 64 -2
50 107 -2
13 70 -10
41 98 -4
53 110 -4
19 76 -8
15 72 -10
39 96 -4
12 69 -10
2 59 2
25 82 -4
49 106 -4
6 63 -2
24 81 -4
10 67 -6
47 104 -6
8 65 -4
42 99 -2
38 95 -4
43 100 0
4 61 -2
26 83 -4
55 112 -4
52 109 -2
22 79 -4
11 68 -8
14 71 -10
48 1...

output:

! ((((((((((()())(()))))))()()()())(()()()))((((())))(()())()))((()())))()(()()(()))(())()(())()()()((()))((()))()()

result:

ok ok

Test #22:

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

input:

114 56
26 83 4
51 108 0
43 100 2
4 61 2
44 101 0
37 94 -4
5 62 0
33 90 -2
45 102 0
22 79 -2
24 81 0
19 76 4
8 65 2
41 98 2
7 64 2
34 91 -4
28 85 4
30 87 2
17 74 4
18 75 6
3 60 4
54 111 -4
21 78 0
38 95 -2
42 99 2
55 112 -6
53 110 -2
13 70 2
23 80 -2
47 104 -2
12 69 0
27 84 4
11 68 2
29 86 2
2 59 6
1...

output:

! (((())))()()(()()(((()))))(()(((((()))))))((())(((((((())()))))()()))(((((()))))((()())())))((((())))())((((()))))

result:

ok ok

Test #23:

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

input:

114 6555
16 65 34
84 110 -27
33 45 13
69 106 -38
17 35 19
28 109 -22
18 66 31
54 90 -29
63 75 -13
4 70 41
62 69 -8
14 62 39
34 88 -7
9 50 42
7 99 9
95 108 -14
31 95 -11
39 59 17
69 88 -20
41 52 12
69 108 -40
24 31 8
34 46 13
16 54 39
12 102 1
51 105 -41
34 69 12
53 94 -32
22 101 -8
30 73 12
46 49 4
...

output:

! ((((((((((((((((((((((((((((((((((((((((((((((((((((((((()))))))))))))))))))))))))))))))))))))))))))))))))))))))))

result:

ok ok

Test #24:

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

input:

114 6555
38 49 0
40 69 0
50 66 1
1 90 2
1 58 2
78 97 0
2 95 0
48 110 1
91 102 0
61 84 0
86 92 1
69 72 0
17 81 -1
74 80 1
49 52 0
17 20 0
10 20 1
37 111 -1
4 7 0
21 41 -1
22 37 0
27 82 0
54 91 0
56 95 0
59 99 -1
64 102 1
85 113 -1
17 22 0
29 29 -1
45 62 0
15 44 0
34 91 0
15 48 0
72 74 1
21 75 -1
35 9...

output:

?

result:

ok ok

Test #25:

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

input:

114 6555
10 44 1
47 69 -1
47 106 0
35 43 -1
49 112 0
46 113 0
30 79 0
63 101 -1
11 16 0
38 111 0
48 86 1
19 51 -1
54 96 1
13 31 -1
68 77 0
48 114 -1
61 111 -1
23 49 -1
50 54 1
42 71 0
20 102 1
12 33 0
48 105 0
12 13 0
44 48 1
38 69 0
5 61 -1
10 100 1
46 102 1
85 101 -1
51 95 -1
23 29 -1
28 50 1
26 1...

output:

! (()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())

result:

ok ok

Test #26:

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

input:

114 6555
14 103 0
58 96 3
42 72 -1
11 26 2
27 110 -10
29 110 -8
12 94 1
50 65 0
29 62 -4
9 90 2
74 105 -2
112 113 0
10 35 2
30 113 -10
57 103 3
28 29 0
7 26 6
43 96 2
7 64 0
6 76 3
66 78 3
46 108 -1
52 62 -1
8 43 0
1 23 11
75 92 2
22 49 -4
55 104 2
55 57 1
36 69 -4
9 50 -2
22 42 -1
11 31 3
78 101 2
...

output:

! ((((((((((())()((()))((()())((()))()()()))))))()(((())()(())()()))((((()(())()(()())(())((((()))((()))))))))))))()

result:

ok ok

Test #27:

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

input:

114 6555
37 43 3
10 42 1
46 98 3
14 108 3
70 76 7
22 86 9
64 72 3
85 87 1
29 54 2
30 57 2
13 21 -1
16 55 4
73 113 -3
26 54 1
44 101 4
95 108 -4
74 84 5
9 9 1
44 76 5
81 110 -6
50 75 6
63 84 10
18 110 1
26 36 -3
47 81 9
11 12 0
9 96 6
2 42 3
89 109 -5
37 101 7
2 56 3
1 74 6
29 100 4
43 66 -2
61 81 11...

output:

! (((()))((()()))(((())))((())))(())()(((()())()()))((((()))))()((()))((((((((((()())((())((())))))))(((()))()))))))

result:

ok ok

Test #28:

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

input:

3000 60614
1358 2885 0
1966 2415 0
198 951 0
1441 2385 1
772 1867 0
1276 2040 -1
122 1065 0
2637 2823 1
780 2281 0
247 1059 1
406 1898 -1
364 2893 0
370 2363 0
1483 2553 1
1820 2537 0
955 2344 0
1543 2263 1
985 1437 1
772 2389 0
1589 2137 1
768 2066 -1
306 676 -1
299 2408 0
371 1875 1
2114 2444 -1
2...

output:

! ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()...

result:

ok ok

Test #29:

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

input:

3000 10507
2159 2394 -236
1195 1922 -116
1944 2128 -185
99 2287 615
360 1811 830
396 2734 -129
891 2961 -851
2376 2584 -209
2072 2608 -537
411 2577 13
1087 1267 181
1613 2846 -1234
376 2112 513
698 804 107
1022 2803 -824
747 1724 530
113 2447 441
503 897 395
1657 2282 -626
936 1403 468
2630 2770 -14...

output:

! ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

result:

ok ok

Test #30:

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

input:

3000 6568
662 925 0
399 2487 -1
524 2228 1
250 1030 1
1381 1704 0
209 2535 -1
1183 2049 -1
95 2463 -1
1703 1798 0
881 1141 -1
272 1454 1
151 2265 -1
1340 2863 0
280 2691 0
1809 2443 -1
1179 2884 0
1326 1393 0
1367 2182 0
400 1868 1
534 1520 1
725 1469 -1
660 1570 1
1543 1950 0
209 1055 -1
1509 1820 ...

output:

?

result:

ok ok

Test #31:

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

input:

3000 80650
1084 2093 0
2 2089 0
562 1090 1
241 1015 -1
661 2585 -1
415 1178 0
619 1977 -1
866 2948 1
408 632 1
216 896 1
361 1329 -1
2091 2531 -1
754 1239 0
409 1798 0
420 2692 1
284 285 0
128 398 1
1475 2468 0
716 819 0
1807 2537 -1
1344 2874 1
1991 2161 -1
574 2598 1
789 2136 0
429 956 0
20 2768 1...

output:

! (()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(...

result:

ok ok

Test #32:

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

input:

3000 33594
1244 1887 0
1323 2778 0
1462 2288 1
261 1146 2
47 2468 -6
800 2288 3
931 2458 0
1020 2905 -10
303 1324 -8
1372 1834 7
956 1909 -4
1386 2969 4
818 2080 -3
80 1377 -4
338 2208 -1
1902 2397 6
873 1626 6
769 1743 -5
312 2914 -7
941 1930 -10
1778 1982 1
338 1857 -2
1386 2703 4
1728 2153 -6
495...

output:

! (((((((((((())(())(()()())(())))((((((((((((())))(())()))))))))))))()((((())(())))(((())())(())))((()(())()((())(()))))))(((()(()))((((()(()))((((((((())))))())))))))((()))()()((())()())((()())(()))(((((()())))(()()()(((()))(()()(()))(())((())))(((()()(()()())))))))((())))(((((((()))((((())()()(((...

result:

ok ok

Test #33:

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

input:

3000 100
119 2964 0
29 2874 0
112 2957 0
57 2902 0
111 2956 0
25 2870 0
131 2976 0
76 2921 0
55 2900 0
99 2944 0
144 2989 0
126 2971 0
133 2978 0
34 2879 0
9 2854 0
37 2882 0
152 2997 0
64 2909 0
44 2889 0
33 2878 0
56 2901 0
77 2922 0
151 2996 0
7 2852 0
75 2920 0
26 2871 0
40 2885 0
42 2887 0
80 2...

output:

! ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()...

result:

ok ok

Test #34:

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

input:

3000 1891
902 1099 198
2788 2985 -198
2609 2806 -198
2535 2732 -198
272 469 198
2206 2403 -198
1251 1448 198
114 311 198
219 416 198
332 529 198
2320 2517 -198
174 371 198
2729 2926 -198
1231 1428 198
509 706 198
997 1194 198
2479 2676 -198
1356 1553 92
2114 2311 -198
1567 1764 -198
2673 2870 -198
1...

output:

! ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

result:

ok ok

Test #35:

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

input:

3000 1230
46 1214 1
330 1498 1
28 1196 1
856 2024 1
217 1385 -1
1557 2725 -1
1037 2205 -1
51 1219 -1
1346 2514 1
179 1347 -1
239 1407 -1
149 1317 -1
1255 2423 -1
237 1405 -1
1476 2644 1
999 2167 -1
144 1312 1
1197 2365 -1
1652 2820 1
146 1314 1
895 2063 -1
915 2083 -1
312 1480 1
900 2068 1
1359 2527...

output:

?

result:

ok ok

Test #36:

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

input:

3000 1062
161 1541 -1
820 2200 1
136 1516 1
1261 2641 -1
1231 2611 -1
84 1464 1
745 2125 -1
766 2146 1
1082 2462 1
77 1457 -1
677 2057 -1
1400 2780 1
1512 2892 1
108 1488 1
914 2294 1
1067 2447 -1
810 2190 1
91 1471 -1
698 2078 1
839 2219 -1
1406 2786 1
1084 2464 1
1041 2421 -1
473 1853 -1
463 1843 ...

output:

! (()())()(()()()())(())()(()()())()()()(()())()(()()()()()()()()()()())()(()())()(())(()()()())(())(())(()()())(()()()()()()()()()()()()()()()()()()()()()())(()()()()()()()()()()())()(()()()()()()()()()())(()()()()()())()(())()()(()()()()()()()()()()()()()()()()()()()())()(()())()(()())(()()()()()(...

result:

ok ok

Test #37:

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

input:

3000 1378
1450 2402 1
1582 2534 -1
1053 2005 1
202 1154 -15
1946 2898 7
1559 2511 -7
1679 2631 -3
161 1113 3
1045 1997 -13
1452 2404 1
74 1026 7
779 1731 -3
788 1740 -3
1529 2481 -1
247 1199 -7
1377 2329 -7
1881 2833 3
341 1293 5
1076 2028 -11
564 1516 1
135 1087 3
2047 2999 -1
982 1934 -5
1843 2795...

output:

! ((()((()())))(())((()()()()()))()()()()(()))(((((()()(())(((())((((())))()()(())())(())))()()))))()(())((((()()()))))((((((())()))(()((())(())))(())()))))()(((()())()(()()((()((()()))((((()(((()(()((())))))))))))))((((()(())))(((((())))(((()()))(((((((()))))()()()))))))(((((()))())()()(((())))))))...

result:

ok ok

Test #38:

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

input:

3000 1499
975 2475 1
956 2456 -1
1416 2916 -1
1426 2926 -1
339 1839 1
585 2085 1
754 2254 -1
712 2212 -1
1419 2919 1
604 2104 -1
600 2100 -1
632 2132 -1
1302 2802 -1
115 1615 1
1257 2757 1
707 2207 1
206 1706 -1
1197 2697 1
606 2106 -1
758 2258 -1
233 1733 1
1225 2725 1
333 1833 1
156 1656 -1
776 22...

output:

! ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()...

result:

ok ok

Test #39:

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

input:

3000 1499
1064 2564 -627
130 1630 1241
800 2300 -99
587 2087 327
1380 2880 -1259
996 2496 -491
1128 2628 -755
32 1532 1437
241 1741 1019
899 2399 -297
70 1570 1361
789 2289 -77
1219 2719 -937
192 1692 1117
613 2113 275
44 1544 1413
1031 2531 -561
1126 2626 -751
576 2076 349
137 1637 1227
460 1960 58...

output:

! ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

result:

ok ok

Test #40:

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

input:

3000 1499
358 1858 1
899 2399 -1
797 2297 -1
1102 2602 1
341 1841 -1
922 2422 1
1115 2615 -1
810 2310 1
1312 2812 1
622 2122 1
1245 2745 -1
9 1509 -1
710 2210 1
947 2447 -1
229 1729 -1
591 2091 -1
334 1834 1
1279 2779 -1
956 2456 1
971 2471 -1
602 2102 1
447 1947 -1
87 1587 -1
1483 2983 -1
1037 2537...

output:

! (()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(...

result:

ok ok

Test #41:

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

input:

3000 1499
682 2182 1
1269 2769 -1
83 1583 -1
112 1612 1
672 2172 1
434 1934 1
399 1899 -1
1324 2824 1
245 1745 -1
358 1858 1
406 1906 1
1090 2590 1
511 2011 -1
424 1924 1
102 1602 1
960 2460 1
42 1542 1
272 1772 1
1176 2676 1
532 2032 1
721 2221 -1
461 1961 -1
912 2412 1
867 2367 -1
202 1702 1
227 1...

output:

! (()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(...

result:

ok ok

Test #42:

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

input:

3000 1499
105 1605 1
506 2006 -9
978 2478 -1
600 2100 -7
1071 2571 -3
1444 2944 3
437 1937 3
507 2007 -11
1331 2831 11
551 2051 -1
1469 2969 -1
206 1706 1
1219 2719 5
67 1567 3
776 2276 3
877 2377 -1
186 1686 -1
1377 2877 7
1105 2605 -3
1091 2591 -3
729 2229 5
1054 2554 -7
843 2343 -3
751 2251 5
230...

output:

! (((((((()))())(()()))((()()())))))(()())()(()((((((()))))())))()()(()((()))())(()())()()()()()()((())(())((()())))((((()(())))))(())((()()())(((()(()()()))()()))((()())(()((()()())))(()))())(()()())(())()(()()()((()(((((())())(()()))((((()))))(()(())(((())))())))))()())()()()()()(((((((()()))))))(...

result:

ok ok

Test #43:

score: 0
Accepted
time: 85ms
memory: 21108kb

input:

3000 500000
28 2927 0
267 2752 0
75 2713 1
214 2973 0
227 2675 1
244 2932 -1
566 2810 -1
96 2628 -1
597 2620 0
742 2934 -1
208 2607 0
38 2317 0
401 2493 1
684 2792 -1
620 2783 0
586 2954 -1
120 2420 -1
516 2940 -1
373 2627 1
385 2638 0
56 2807 0
188 2812 -1
542 2861 0
81 2439 1
618 2696 -1
858 2932 ...

output:

! ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()...

result:

ok ok

Test #44:

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

input:

3000 500000
187 2890 -76
942 2982 -923
313 2497 191
740 2962 -701
161 2437 403
754 2828 -581
100 2964 -63
333 2688 -20
39 2643 319
337 2466 198
277 2630 94
425 2752 -176
22 2223 756
518 2730 -247
271 2619 111
246 2830 -75
476 2617 -92
657 2894 -550
95 2651 255
508 2574 -81
430 2737 -166
305 2578 118...

output:

! ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

result:

ok ok

Test #45:

score: 0
Accepted
time: 544ms
memory: 20820kb

input:

3000 500000
483 2906 0
247 2934 0
626 2956 1
699 2712 0
453 2748 0
73 2710 0
91 2180 0
41 2584 0
41 2971 -1
130 2803 0
213 2598 0
232 2650 1
737 2808 0
772 2947 0
16 2684 1
871 2977 -1
252 2856 1
78 2209 0
415 2943 -1
155 2697 -1
75 2339 -1
55 2147 -1
183 2851 -1
88 2639 0
566 2620 1
745 2753 -1
24 ...

output:

?

result:

ok ok

Test #46:

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

input:

3000 500000
13 2850 0
518 2712 1
447 2542 0
557 2667 -1
112 2916 1
280 2612 1
787 2873 -1
60 2365 0
557 2817 -1
340 2426 1
406 2569 0
387 2905 -1
258 2424 1
741 2973 -1
187 2775 -1
208 2980 1
837 2886 0
105 2632 0
209 2895 -1
65 2991 -1
727 2995 -1
111 2964 0
233 2729 -1
601 2794 0
350 2419 0
383 26...

output:

! (()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(...

result:

ok ok

Test #47:

score: 0
Accepted
time: 81ms
memory: 20844kb

input:

3000 500000
850 2963 0
259 2308 4
184 2198 5
151 2492 0
27 2717 11
361 2702 0
247 2320 4
754 2758 13
926 2993 -2
431 2489 -5
407 2488 -6
439 2853 1
288 2402 7
623 2859 -1
179 2504 12
476 2993 -10
639 2908 6
721 2958 -6
697 2951 -3
375 2458 -4
462 2476 -7
301 2778 16
618 2902 5
388 2545 -6
494 2699 0...

output:

! (((()()(((())((()()()()))))(())()())))(((((((((((()()))(((())()))))))))(((((((()())()()((()(())()))))()(((())))((())((()))))((()))()(()(((((())()))))(()())((((()))))(())())))))))((((()))))(())(()()())(())(((((((((((())(())(()))((()))))))))())((())(((((()())()))))))(())((((((())(()))))()()()((())))...

result:

ok ok

Test #48:

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

input:

3000 1827
138 141 0
1761 1763 1
1787 1787 1
2253 2253 1
457 457 1
1160 1160 -1
217 217 1
724 726 -1
2341 2345 1
1567 1568 0
1779 1779 1
1354 1354 -1
1306 1307 0
2198 2198 -1
1732 1735 0
2736 2736 -1
222 222 -1
1009 1010 0
1166 1169 0
1474 1476 -1
1962 1963 0
1318 1318 -1
1133 1133 1
2523 2523 1
1883...

output:

! ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()...

result:

ok ok

Test #49:

score: -100
Wrong Answer
time: 0ms
memory: 7716kb

input:

3000 1783
2244 2244 -1
1770 1770 -1
1334 1336 3
2295 2295 -1
1127 1127 1
774 774 1
1358 1358 1
2372 2372 -1
2730 2730 -1
2215 2216 -2
389 389 1
2887 2887 -1
746 746 1
2309 2309 -1
2907 2910 -4
2769 2769 -1
1030 1030 1
2630 2630 -1
78 81 4
2542 2543 -2
1624 1624 -1
2520 2520 -1
518 518 1
1163 1163 1
...

output:

?

result:

wrong answer participant reports no solution but jury has one