QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#554917	#8559. $k$-coloring	PhantomThreshold^#	AC ✓	88ms	31472kb	C++20	5.5kb	2024-09-09 17:56:04	2024-09-09 17:56:05

Judging History

This is the latest submission verdict.

[2024-09-09 17:56:05]
Judged

Verdict: AC
Time: 88ms
Memory: 31472kb

Show

[2024-09-09 17:56:04]
Submitted

answer

#include<bits/stdc++.h>
using namespace std;

const int maxn=233333;
int n,m;
int e[maxn][2];
int d[maxn],use[maxn];
struct edge
{
    int y,i,nex;
}a[maxn<<1];
int len,fir[maxn];
void ins(int x,int y,int i)
{
    a[++len]=(edge){y,i,fir[x]};fir[x]=len;
}
int t[maxn],tp;
void dfs(const int x)
{
    for(int &k=fir[x],y=a[k].y;k;y=a[k].y)
    {
        if(use[a[k].i])
        {
            k=a[k].nex;
            continue;
        }
        int tk=a[k].i;use[tk]=1;k=a[k].nex;
        dfs(y);
        t[++tp]=tk;
        if(x==e[tk][1])t[tp]*=-1;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    int k;
    cin>>n>>m>>k;
    vector<vector<int>> G(n+5),T(n+m+5);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        e[i][0]=u;
        e[i][1]=v;
        ins(u,v,i);
        ins(v,u,i);
        d[u]^=1;d[v]^=1;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    if(k==1)
    {
        int cntd1=0,spv=0;
        for(int i=1;i<=n;i++)
        {
            if(d[i])cntd1++,spv=i;
        }
        if(cntd1>2 or (cntd1==2 and not d[1]))
        {
            cout<<-1<<endl;
            return 0;
        }
        if(cntd1==2)
        {
            m++;
            int u=1,v=spv;
            e[m][0]=u;
            e[m][1]=v;
            ins(u,v,m);
            ins(v,u,m);
            d[u]^=1;d[v]^=1;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        for(int i=1;i<=n;i++)
        {
            if(fir[i])
            {
                dfs(i);
                break;
            }
        }
        if(tp!=m)
        {
            cout<<-1<<endl;
            return 0;
        }
        vector<int> ord;
        if(not spv)
        {
            ord.push_back(1);
        }
        for(int i=tp;i>=1;i--)
        {
            if(t[i]>0)
                ord.push_back(e[t[i]][1]);
            else
                ord.push_back(e[-t[i]][0]);
        }
        if(spv)
        {
            int pos=0;
            for(int i=0;i+1<(int)ord.size();i++)
            {
                if(ord[i]==1 and ord[i+1]==spv)
                {
                    pos=i+1;
                    break;
                }
                if(ord[i]==spv and ord[i+1]==1)
                {
                    pos=i+1;
                    break;
                }
            }
            rotate(ord.begin(),ord.begin()+pos,ord.end());
            if(ord[0]!=1)reverse(ord.begin(),ord.end());
        }
        cout<<ord.size()<<endl;
        for(auto z:ord)
        {
            cout<<z<<" ";
        }
    }
    else
    {
        vector<int> idx(n+m+5),vis(n+5),pa(n+m+5),dep(n+m+5);
        int top=n;
        vector<pair<int,int>> ord0;
        function<void(int,int)> dfs1=[&](int u,int p)
        {
  //          cerr<<"dfs "<<u<<' '<<p<<endl;
            vis[u]=1;
            idx[u]=u;
            for(auto v:G[u])
            {
                if(p==v)continue;
   //             cerr<<"! "<<u<<' '<<v<<endl;
                if(not vis[v])
                {
                    if(dep[u]%2==1)ord0.emplace_back(u,v);
                    T[u].push_back(v);
                    pa[v]=u;dep[v]=dep[u]+1;
                    dfs1(v,u);
                    if(dep[u]%2==0)ord0.emplace_back(u,v);
                }
                else if(vis[v]==1)
                {
                    int t=++top;
                    if(dep[u]%2==1)ord0.emplace_back(u,t);
                    T[u].push_back(t);
                    pa[t]=u;dep[t]=dep[u]+1;
                    idx[t]=v;
                    if(dep[u]%2==0)ord0.emplace_back(u,t);
                }
            }
            vis[u]=2;
  //          cerr<<"ret "<<u<<endl;
        };
        dfs1(1,0);
        auto lca=[&](int x,int y)
        {
            while(x!=y)
            {
                if(dep[x]>dep[y])x=pa[x];
                else y=pa[y];
            }
            return x;
        };
        vector<int> ord;
        ord.push_back(1);
        int cur=1;
        for(auto [u,v]:ord0)
        {
  //          cerr<<"go "<<u<<' '<<v<<endl;
            int tt=k;
            //phase 1
            int lu=lca(cur,u),lv=lca(cur,v);
            int du=dep[cur]+dep[u]-2*dep[lu],dv=dep[cur]+dep[v]-2*dep[lv];
            if(du>dv)swap(u,v),swap(lu,lv);
            vector<int> tmpu,tmpd;
            int t=cur;
            while(t!=lu)
            {
                tmpu.push_back(pa[t]);
                t=pa[t];
            }
            t=u;
            while(t!=lu)
            {
                tmpd.push_back(t);
                t=pa[t];
            }
            reverse(tmpd.begin(),tmpd.end());
            for(auto z:tmpu)
            {
                ord.push_back(idx[z]);
                tt--;
            }
            for(auto z:tmpd)
            {
                ord.push_back(idx[z]);
                tt--;
            }
            cur=u;
            //phase 2
            while(tt>0)
            {
                if(cur==u)
                {
                    ord.push_back(idx[v]);
                    cur=v;
                    tt--;
                }
                else
                {
                    ord.push_back(idx[u]);
                    cur=u;
                    tt--;
                }
            }
        };
        cout<<ord.size()<<endl;
        for(auto z:ord)
        {
            cout<<z<<" ";
        }
    }
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 5560kb

input:

output:

4
1 3 2 1

result:

ok Success

Test #2:

score: 0

Accepted

time: 1ms

memory: 5624kb

input:

output:

7
1 2 3 1 3 2 1

result:

ok Success

Test #3:

score: 0

Accepted

time: 1ms

memory: 5600kb

input:

output:

4
1 3 4 2

result:

ok Success

Test #4:

score: 0

Accepted

time: 0ms

memory: 5564kb

input:

output:

5
1 4 2 3 1

result:

ok Success

Test #5:

score: 0

Accepted

time: 0ms

memory: 7904kb

input:

output:

6
1 5 2 4 3 5

result:

ok Success

Test #6:

score: 0

Accepted

time: 0ms

memory: 5864kb

input:

output:

11
1 5 4 3 5 2 4 1 3 2 1

result:

ok Success

Test #7:

score: 0

Accepted

time: 0ms

memory: 5632kb

input:

output:

6
1 2 5 3 4 6

result:

ok Success

Test #8:

score: 0

Accepted

time: 0ms

memory: 5616kb

input:

output:

7
1 2 5 4 3 6 1

result:

ok Success

Test #9:

score: 0

Accepted

time: 1ms

memory: 5672kb

input:

output:

8
1 5 3 6 2 3 4 6

result:

ok Success

Test #10:

score: 0

Accepted

time: 0ms

memory: 5696kb

input:

output:

9
1 6 5 3 4 1 2 4 6

result:

ok Success

Test #11:

score: 0

Accepted

time: 1ms

memory: 5908kb

input:

output:

10
1 4 2 1 5 4 3 6 5 3

result:

ok Success

Test #12:

score: 0

Accepted

time: 0ms

memory: 7740kb

input:

output:

11
1 2 4 6 2 5 6 3 4 1 6

result:

ok Success

Test #13:

score: 0

Accepted

time: 1ms

memory: 5660kb

input:

output:

12
1 3 2 1 5 4 1 6 4 2 6 3

result:

ok Success

Test #14:

score: 0

Accepted

time: 1ms

memory: 5560kb

input:

output:

22
1 7 6 5 7 4 6 3 7 2 6 1 5 4 3 5 2 4 1 3 2 1

result:

ok Success

Test #15:

score: 0

Accepted

time: 1ms

memory: 7740kb

input:

output:

-1

result:

ok Success

Test #16:

score: 0

Accepted

time: 0ms

memory: 5696kb

input:

output:

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

result:

ok Success

Test #17:

score: 0

Accepted

time: 1ms

memory: 5884kb

input:

output:

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

result:

ok Success

Test #18:

score: 0

Accepted

time: 1ms

memory: 6028kb

input:

output:

1001
1 82 24 52 29 60 58 22 94 54 99 79 20 34 5 18 83 63 66 37 44 31 8 48 55 21 62 27 19 15 75 9 81 74 6 89 36 34 98 30 72 87 21 52 96 53 85 36 79 48 42 91 43 96 51 45 22 54 9 80 100 70 50 93 86 33 28 58 69 64 23 26 87 11 46 45 93 17 35 75 87 17 11 7 20 32 12 98 89 61 24 90 88 56 89 49 73 68 17 6 43...

result:

ok Success

Test #19:

score: 0

Accepted

time: 10ms

memory: 9896kb

input:

400 79800 1
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
1 6
2 6
3 6
4 6
5 6
1 7
2 7
3 7
4 7
5 7
6 7
1 8
2 8
3 8
4 8
5 8
6 8
7 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
1 11
2 11
3 11
4 11
5 11
6 11
7 11
8 11
9 11
10 11
1 12
2 12
3 12
4 12
5 12
6 12
7 12
8 12
9 12
10 ...

output:

-1

result:

ok Success

Test #20:

score: 0

Accepted

time: 14ms

memory: 19856kb

input:

401 80200 1
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
1 6
2 6
3 6
4 6
5 6
1 7
2 7
3 7
4 7
5 7
6 7
1 8
2 8
3 8
4 8
5 8
6 8
7 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
1 11
2 11
3 11
4 11
5 11
6 11
7 11
8 11
9 11
10 11
1 12
2 12
3 12
4 12
5 12
6 12
7 12
8 12
9 12
10 ...

output:

80201
1 401 400 399 401 398 400 397 401 396 400 395 401 394 400 393 401 392 400 391 401 390 400 389 401 388 400 387 401 386 400 385 401 384 400 383 401 382 400 381 401 380 400 379 401 378 400 377 401 376 400 375 401 374 400 373 401 372 400 371 401 370 400 369 401 368 400 367 401 366 400 365 401 364 ...

result:

ok Success

Test #21:

score: 0

Accepted

time: 20ms

memory: 16532kb

input:

400 79800 2
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
1 6
2 6
3 6
4 6
5 6
1 7
2 7
3 7
4 7
5 7
6 7
1 8
2 8
3 8
4 8
5 8
6 8
7 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
1 11
2 11
3 11
4 11
5 11
6 11
7 11
8 11
9 11
10 11
1 12
2 12
3 12
4 12
5 12
6 12
7 12
8 12
9 12
10 ...

output:

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

result:

ok Success

Test #22:

score: 0

Accepted

time: 10ms

memory: 16056kb

input:

401 80200 2
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
1 6
2 6
3 6
4 6
5 6
1 7
2 7
3 7
4 7
5 7
6 7
1 8
2 8
3 8
4 8
5 8
6 8
7 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
1 11
2 11
3 11
4 11
5 11
6 11
7 11
8 11
9 11
10 11
1 12
2 12
3 12
4 12
5 12
6 12
7 12
8 12
9 12
10 ...

output:

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

result:

ok Success

Test #23:

score: 0

Accepted

time: 19ms

memory: 13776kb

input:

400 79800 3
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
1 6
2 6
3 6
4 6
5 6
1 7
2 7
3 7
4 7
5 7
6 7
1 8
2 8
3 8
4 8
5 8
6 8
7 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
1 11
2 11
3 11
4 11
5 11
6 11
7 11
8 11
9 11
10 11
1 12
2 12
3 12
4 12
5 12
6 12
7 12
8 12
9 12
10 ...

output:

239401
1 2 3 2 3 1 3 4 1 4 2 4 2 4 5 4 5 1 5 2 5 2 5 3 5 6 1 6 2 6 2 6 3 6 4 6 4 6 7 6 7 1 7 2 7 2 7 3 7 4 7 4 7 5 7 8 1 8 2 8 2 8 3 8 4 8 4 8 5 8 6 8 6 8 9 8 9 1 9 2 9 2 9 3 9 4 9 4 9 5 9 6 9 6 9 7 9 10 1 10 2 10 2 10 3 10 4 10 4 10 5 10 6 10 6 10 7 10 8 10 8 10 11 10 11 1 11 2 11 2 11 3 11 4 11 4 ...

result:

ok Success

Test #24:

score: 0

Accepted

time: 12ms

memory: 16452kb

input:

401 80200 3
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
1 6
2 6
3 6
4 6
5 6
1 7
2 7
3 7
4 7
5 7
6 7
1 8
2 8
3 8
4 8
5 8
6 8
7 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
1 11
2 11
3 11
4 11
5 11
6 11
7 11
8 11
9 11
10 11
1 12
2 12
3 12
4 12
5 12
6 12
7 12
8 12
9 12
10 ...

output:

240601
1 2 3 2 3 1 3 4 1 4 2 4 2 4 5 4 5 1 5 2 5 2 5 3 5 6 1 6 2 6 2 6 3 6 4 6 4 6 7 6 7 1 7 2 7 2 7 3 7 4 7 4 7 5 7 8 1 8 2 8 2 8 3 8 4 8 4 8 5 8 6 8 6 8 9 8 9 1 9 2 9 2 9 3 9 4 9 4 9 5 9 6 9 6 9 7 9 10 1 10 2 10 2 10 3 10 4 10 4 10 5 10 6 10 6 10 7 10 8 10 8 10 11 10 11 1 11 2 11 2 11 3 11 4 11 4 ...

result:

ok Success

Test #25:

score: 0

Accepted

time: 23ms

memory: 16816kb

input:

400 79800 4
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
1 6
2 6
3 6
4 6
5 6
1 7
2 7
3 7
4 7
5 7
6 7
1 8
2 8
3 8
4 8
5 8
6 8
7 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
1 11
2 11
3 11
4 11
5 11
6 11
7 11
8 11
9 11
10 11
1 12
2 12
3 12
4 12
5 12
6 12
7 12
8 12
9 12
10 ...

output:

319201
1 2 3 2 3 1 3 1 3 4 1 4 1 4 2 4 2 4 5 4 5 1 5 1 5 2 5 2 5 3 5 3 5 6 1 6 1 6 2 6 2 6 3 6 3 6 4 6 4 6 7 6 7 1 7 1 7 2 7 2 7 3 7 3 7 4 7 4 7 5 7 5 7 8 1 8 1 8 2 8 2 8 3 8 3 8 4 8 4 8 5 8 5 8 6 8 6 8 9 8 9 1 9 1 9 2 9 2 9 3 9 3 9 4 9 4 9 5 9 5 9 6 9 6 9 7 9 7 9 10 1 10 1 10 2 10 2 10 3 10 3 10 4 ...

result:

ok Success

Test #26:

score: 0

Accepted

time: 29ms

memory: 15848kb

input:

401 80200 4
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
1 6
2 6
3 6
4 6
5 6
1 7
2 7
3 7
4 7
5 7
6 7
1 8
2 8
3 8
4 8
5 8
6 8
7 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
1 11
2 11
3 11
4 11
5 11
6 11
7 11
8 11
9 11
10 11
1 12
2 12
3 12
4 12
5 12
6 12
7 12
8 12
9 12
10 ...

output:

320801
1 2 3 2 3 1 3 1 3 4 1 4 1 4 2 4 2 4 5 4 5 1 5 1 5 2 5 2 5 3 5 3 5 6 1 6 1 6 2 6 2 6 3 6 3 6 4 6 4 6 7 6 7 1 7 1 7 2 7 2 7 3 7 3 7 4 7 4 7 5 7 5 7 8 1 8 1 8 2 8 2 8 3 8 3 8 4 8 4 8 5 8 5 8 6 8 6 8 9 8 9 1 9 1 9 2 9 2 9 3 9 3 9 4 9 4 9 5 9 5 9 6 9 6 9 7 9 7 9 10 1 10 1 10 2 10 2 10 3 10 3 10 4 ...

result:

ok Success

Test #27:

score: 0

Accepted

time: 27ms

memory: 16492kb

input:

400 79800 5
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
1 6
2 6
3 6
4 6
5 6
1 7
2 7
3 7
4 7
5 7
6 7
1 8
2 8
3 8
4 8
5 8
6 8
7 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
1 11
2 11
3 11
4 11
5 11
6 11
7 11
8 11
9 11
10 11
1 12
2 12
3 12
4 12
5 12
6 12
7 12
8 12
9 12
10 ...

output:

399001
1 2 3 2 3 2 3 1 3 1 3 4 1 4 1 4 2 4 2 4 2 4 5 4 5 4 5 1 5 1 5 2 5 2 5 2 5 3 5 3 5 6 1 6 1 6 2 6 2 6 2 6 3 6 3 6 4 6 4 6 4 6 7 6 7 6 7 1 7 1 7 2 7 2 7 2 7 3 7 3 7 4 7 4 7 4 7 5 7 5 7 8 1 8 1 8 2 8 2 8 2 8 3 8 3 8 4 8 4 8 4 8 5 8 5 8 6 8 6 8 6 8 9 8 9 8 9 1 9 1 9 2 9 2 9 2 9 3 9 3 9 4 9 4 9 4 9...

result:

ok Success

Test #28:

score: 0

Accepted

time: 27ms

memory: 19640kb

input:

401 80200 7
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
1 6
2 6
3 6
4 6
5 6
1 7
2 7
3 7
4 7
5 7
6 7
1 8
2 8
3 8
4 8
5 8
6 8
7 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
1 11
2 11
3 11
4 11
5 11
6 11
7 11
8 11
9 11
10 11
1 12
2 12
3 12
4 12
5 12
6 12
7 12
8 12
9 12
10 ...

output:

561401
1 2 3 2 3 2 3 2 3 1 3 1 3 1 3 4 1 4 1 4 1 4 2 4 2 4 2 4 2 4 5 4 5 4 5 4 5 1 5 1 5 1 5 2 5 2 5 2 5 2 5 3 5 3 5 3 5 6 1 6 1 6 1 6 2 6 2 6 2 6 2 6 3 6 3 6 3 6 4 6 4 6 4 6 4 6 7 6 7 6 7 6 7 1 7 1 7 1 7 2 7 2 7 2 7 2 7 3 7 3 7 3 7 4 7 4 7 4 7 4 7 5 7 5 7 5 7 8 1 8 1 8 1 8 2 8 2 8 2 8 2 8 3 8 3 8 3...

result:

ok Success

Test #29:

score: 0

Accepted

time: 48ms

memory: 18004kb

input:

400 79800 10
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
1 6
2 6
3 6
4 6
5 6
1 7
2 7
3 7
4 7
5 7
6 7
1 8
2 8
3 8
4 8
5 8
6 8
7 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
1 11
2 11
3 11
4 11
5 11
6 11
7 11
8 11
9 11
10 11
1 12
2 12
3 12
4 12
5 12
6 12
7 12
8 12
9 12
10...

output:

798001
1 2 3 2 3 2 3 2 3 2 3 1 3 1 3 1 3 1 3 1 3 4 1 4 1 4 1 4 1 4 1 4 2 4 2 4 2 4 2 4 2 4 5 4 5 4 5 4 5 4 5 1 5 1 5 1 5 1 5 1 5 2 5 2 5 2 5 2 5 2 5 3 5 3 5 3 5 3 5 3 5 6 1 6 1 6 1 6 1 6 1 6 2 6 2 6 2 6 2 6 2 6 3 6 3 6 3 6 3 6 3 6 4 6 4 6 4 6 4 6 4 6 7 6 7 6 7 6 7 6 7 1 7 1 7 1 7 1 7 1 7 2 7 2 7 2 7...

result:

ok Success

Test #30:

score: 0

Accepted

time: 1ms

memory: 5660kb

input:

output:

-1

result:

ok Success

Test #31:

score: 0

Accepted

time: 0ms

memory: 7664kb

input:

output:

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

result:

ok Success

Test #32:

score: 0

Accepted

time: 0ms

memory: 5664kb

input:

output:

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

result:

ok Success

Test #33:

score: 0

Accepted

time: 0ms

memory: 7680kb

input:

output:

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

result:

ok Success

Test #34:

score: 0

Accepted

time: 1ms

memory: 5716kb

input:

output:

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

result:

ok Success

Test #35:

score: 0

Accepted

time: 1ms

memory: 5600kb

input:

output:

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

result:

ok Success

Test #36:

score: 0

Accepted

time: 0ms

memory: 7672kb

input:

output:

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

result:

ok Success

Test #37:

score: 0

Accepted

time: 0ms

memory: 5600kb

input:

output:

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

result:

ok Success

Test #38:

score: 0

Accepted

time: 1ms

memory: 7876kb

input:

output:

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

result:

ok Success

Test #39:

score: 0

Accepted

time: 1ms

memory: 7712kb

input:

output:

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

result:

ok Success

Test #40:

score: 0

Accepted

time: 0ms

memory: 5692kb

input:

output:

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

result:

ok Success

Test #41:

score: 0

Accepted

time: 1ms

memory: 5664kb

input:

output:

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

result:

ok Success

Test #42:

score: 0

Accepted

time: 1ms

memory: 7904kb

input:

output:

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

result:

ok Success

Test #43:

score: 0

Accepted

time: 1ms

memory: 5832kb

input:

output:

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

result:

ok Success

Test #44:

score: 0

Accepted

time: 1ms

memory: 7664kb

input:

output:

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

result:

ok Success

Test #45:

score: 0

Accepted

time: 1ms

memory: 5560kb

input:

output:

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

result:

ok Success

Test #46:

score: 0

Accepted

time: 0ms

memory: 7648kb

input:

output:

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

result:

ok Success

Test #47:

score: 0

Accepted

time: 0ms

memory: 7656kb

input:

output:

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

result:

ok Success

Test #48:

score: 0

Accepted

time: 0ms

memory: 5696kb

input:

output:

298
1 43 52 43 52 99 52 43 78 43 78 51 15 51 59 51 78 51 78 46 62 46 62 14 62 46 17 46 17 49 17 80 18 80 18 89 18 80 17 80 17 46 65 29 60 29 60 11 60 19 44 19 60 19 60 88 55 88 55 37 35 81 35 81 35 74 27 74 35 74 35 37 5 37 55 37 55 88 60 29 93 29 93 50 93 79 93 79 93 42 66 42 93 42 93 29 65 96 65 9...

result:

ok Success

Test #49:

score: 0

Accepted

time: 0ms

memory: 7956kb

input:

output:

199
1 58 98 58 1 6 45 5 45 83 45 8 45 50 87 33 87 50 36 42 36 50 14 86 73 86 74 86 21 47 39 99 39 47 21 18 11 18 21 86 53 13 43 20 43 17 92 17 43 13 44 13 56 88 66 88 72 88 56 31 56 12 29 12 56 89 56 57 78 57 2 57 54 57 56 13 53 26 7 15 27 62 27 46 67 46 75 46 70 79 28 59 28 79 70 3 41 3 70 16 70 63...

result:

ok Success

Test #50:

score: 0

Accepted

time: 0ms

memory: 7784kb

input:

output:

2001
1 70 69 57 83 38 46 61 81 10 19 1 19 21 78 47 84 98 39 18 79 9 96 50 11 2 74 49 51 64 23 66 68 31 8 67 57 67 71 40 7 96 7 33 57 33 49 33 21 33 90 1 90 92 1 92 53 1 53 28 84 28 52 11 52 74 52 17 29 38 29 12 45 44 54 26 81 26 17 26 37 18 37 12 37 9 37 15 42 69 42 65 88 62 79 62 1 62 89 34 95 80 1...

result:

ok Success

Test #51:

score: 0

Accepted

time: 0ms

memory: 7796kb

input:

output:

4003
1 61 94 30 70 18 40 81 66 55 98 38 20 7 89 37 58 16 36 100 74 64 77 31 70 31 39 21 24 11 17 42 99 86 36 86 28 57 41 58 41 78 34 63 14 35 51 32 13 53 5 40 5 78 5 27 56 47 76 19 72 67 63 67 7 67 85 82 26 49 33 1 33 7 33 83 53 83 9 87 84 38 84 61 84 64 84 54 77 54 36 54 3 43 51 43 12 45 52 15 17 1...

result:

ok Success

Test #52:

score: 0

Accepted

time: 2ms

memory: 8140kb

input:

output:

9111
1 21 38 88 81 13 38 13 74 57 40 63 60 56 26 22 89 90 59 65 72 51 73 27 58 8 11 48 86 18 10 50 54 36 62 66 86 66 45 39 37 26 37 95 9 41 6 75 29 73 29 11 29 58 29 37 29 19 44 91 78 4 67 84 16 81 16 50 16 90 16 100 12 15 36 15 38 15 89 15 14 28 3 73 3 68 41 68 73 68 79 42 61 70 46 85 23 62 23 52 2...

result:

ok Success

Test #53:

score: 0

Accepted

time: 2ms

memory: 8020kb

input:

output:

3001
1 30 17 30 17 5 10 29 67 29 67 88 16 61 34 61 34 3 60 66 42 66 42 11 100 61 100 61 100 7 81 2 13 2 13 97 58 8 85 8 85 88 85 42 85 42 85 26 27 40 47 40 47 58 47 96 1 96 70 96 70 32 44 32 44 43 54 71 95 71 95 2 95 100 95 100 95 97 95 13 95 13 95 39 25 80 46 80 46 68 1 68 63 68 63 71 63 69 23 69 2...

result:

ok Success

Test #54:

score: 0

Accepted

time: 0ms

memory: 5952kb

input:

output:

6004
1 38 85 38 85 73 43 60 18 60 18 96 85 96 87 96 87 36 5 54 26 54 26 35 9 99 39 99 39 95 73 95 35 95 76 95 76 18 76 18 76 63 50 87 50 87 50 64 51 14 56 14 56 83 68 32 1 32 49 32 49 47 92 47 92 42 21 18 21 18 21 1 21 2 57 2 57 68 57 13 77 13 77 61 71 75 8 75 8 28 39 28 38 28 94 28 94 44 17 44 17 1...

result:

ok Success

Test #55:

score: 0

Accepted

time: 2ms

memory: 8224kb

input:

output:

13666
1 66 29 66 29 54 45 69 8 69 8 17 52 35 75 35 75 96 12 16 79 16 79 29 79 90 73 90 73 59 8 59 27 59 27 9 69 9 77 9 77 34 50 94 76 94 76 52 76 4 43 4 43 62 96 62 91 62 91 99 75 99 9 99 5 99 5 77 5 77 5 93 55 42 61 42 61 85 72 17 72 17 72 22 20 88 25 88 25 47 7 23 55 23 93 23 93 23 44 23 44 89 30 ...

result:

ok Success

Test #56:

score: 0

Accepted

time: 0ms

memory: 7936kb

input:

output:

2998
1 573 7 573 1 573 1 862 342 862 973 862 973 862 691 862 691 18 926 335 926 335 926 18 423 421 423 421 423 770 709 770 423 770 423 54 423 18 364 18 72 18 72 974 72 974 72 18 614 873 540 873 540 790 540 53 161 53 161 180 161 53 800 53 800 867 800 53 798 53 540 53 540 873 86 873 666 873 666 138 77...

result:

ok Success

Test #57:

score: 0

Accepted

time: 1ms

memory: 6092kb

input:

output:

1999
1 272 612 62 612 319 758 319 612 272 603 365 826 365 972 106 972 365 524 958 524 967 636 201 636 967 184 246 184 384 327 384 849 384 184 967 524 100 604 247 321 247 604 527 604 234 797 234 604 100 524 742 524 553 113 553 596 553 802 136 802 708 710 708 802 553 524 365 800 918 492 918 800 365 60...

result:

ok Success

Test #58:

score: 0

Accepted

time: 1ms

memory: 5872kb

input:

1000 1000 2
125 103
864 747
548 614
588 136
751 946
767 271
975 412
801 382
966 219
28 458
796 450
664 314
604 983
148 487
752 279
323 597
916 326
723 606
322 877
92 55
728 548
210 585
79 677
296 719
826 420
210 551
593 298
973 130
909 918
86 506
748 740
483 829
737 978
193 28
984 558
967 94
363 338...

output:

2001
1 275 238 275 26 501 910 216 881 216 452 216 910 211 910 501 26 476 26 196 86 506 73 730 73 506 800 849 705 497 847 497 705 815 705 849 800 506 396 673 396 506 86 483 829 429 829 879 706 879 829 483 780 189 485 189 780 483 927 426 896 426 994 819 24 819 308 819 994 426 927 483 636 931 79 677 79...

result:

ok Success

Test #59:

score: 0

Accepted

time: 2ms

memory: 8008kb

input:

1000 2001 2
675 964
46 1
347 50
572 1
572 545
315 515
107 1
527 725
480 1
436 894
579 550
754 544
388 749
748 308
791 806
634 788
360 314
304 1
21 1
965 214
128 1
658 1
857 756
133 1
284 595
179 399
127 486
535 28
96 1
652 1
664 1
873 386
367 613
248 1
33 1
753 414
997 999
333 1
595 171
211 536
685 ...

output:

4003
1 46 11 1 11 519 347 50 1 50 29 421 617 1 617 309 163 912 200 1 200 912 163 1 163 15 839 440 420 1 420 370 777 137 673 805 186 187 776 187 556 193 1 193 720 578 720 803 1 803 595 284 247 814 79 1 79 451 19 128 1 128 627 1 627 524 209 665 956 986 860 1 860 270 35 631 198 1 198 277 958 890 1 890 ...

result:

ok Success

Test #60:

score: 0

Accepted

time: 4ms

memory: 6576kb

input:

1000 10001 2
749 878
604 171
92 876
628 888
720 612
136 336
142 510
510 978
402 503
565 199
872 70
120 423
981 42
974 1
205 377
105 556
495 925
277 1
92 231
85 592
896 173
834 496
639 872
794 705
427 684
870 478
686 110
115 1
751 14
715 692
676 202
816 858
750 491
435 796
193 264
614 290
417 1
102 4...

output:

20003
1 974 507 326 908 1 908 65 647 928 895 256 716 715 692 230 857 980 185 523 579 174 584 337 783 410 857 410 710 180 541 446 365 629 655 35 441 547 1 547 510 142 549 610 438 683 625 694 187 480 234 80 875 293 362 968 433 152 509 999 1 999 990 1 990 403 66 211 255 127 73 755 580 287 191 272 931 3...

result:

ok Success

Test #61:

score: 0

Accepted

time: 1ms

memory: 5824kb

input:

1000 1000 3
89 11
717 647
270 15
415 232
453 331
245 436
843 389
140 660
785 64
948 671
485 2
843 460
395 945
631 10
809 525
68 422
578 984
919 373
909 558
812 223
150 54
927 442
370 440
412 20
74 81
165 782
507 600
330 800
311 147
91 399
871 330
984 444
118 635
936 222
346 250
141 531
804 573
586 2...

output:

3001
1 352 615 352 615 744 547 744 629 744 629 191 376 191 629 191 629 876 369 848 988 848 369 848 369 135 84 135 84 18 439 218 276 218 682 218 682 218 161 218 439 218 439 258 439 258 439 18 84 544 84 544 84 814 84 135 567 135 369 135 369 876 536 876 536 102 536 900 423 900 423 288 989 288 898 288 4...

result:

ok Success

Test #62:

score: 0

Accepted

time: 2ms

memory: 8268kb

input:

1000 2001 3
388 1
49 533
452 1
470 596
860 730
929 704
173 875
98 74
898 400
569 62
677 745
895 1
734 959
78 478
857 672
625 200
581 662
750 1
234 1
583 433
613 844
975 1
99 423
398 31
625 692
661 690
647 594
98 1
44 1
834 93
368 21
685 955
75 617
728 1
37 801
668 649
736 368
573 150
473 341
18 979
...

output:

6004
1 388 850 388 850 871 943 204 547 204 547 558 739 917 1 917 204 917 204 917 940 917 940 1 940 102 81 102 81 1 81 370 643 370 643 1 643 146 236 146 236 319 1 319 774 319 774 347 97 535 688 535 688 9 29 1 29 1 29 9 351 1 351 1 351 9 280 763 382 763 382 1 382 763 766 763 766 879 1 879 766 879 766 ...

result:

ok Success

Test #63:

score: 0

Accepted

time: 0ms

memory: 8628kb

input:

1000 10001 3
527 713
208 718
138 417
122 428
687 863
131 600
241 853
442 896
950 237
583 701
208 732
466 219
13 73
592 887
760 668
441 245
137 97
438 663
493 785
86 901
200 75
736 343
135 318
566 550
936 601
120 246
729 341
624 849
757 115
887 404
771 952
784 241
39 518
352 479
840 752
900 960
891 6...

output:

30004
1 474 280 474 280 136 108 805 530 805 530 78 652 734 1 734 187 734 187 689 983 689 983 53 49 574 985 574 985 154 664 57 771 57 771 952 1 952 268 952 268 199 815 641 142 641 142 925 893 413 823 413 823 176 98 677 228 677 228 369 623 273 783 273 783 272 327 239 366 239 366 189 443 300 89 300 89 ...

result:

ok Success

Test #64:

score: 0

Accepted

time: 37ms

memory: 26460kb

input:

100000 100000 2
82663 79676
83623 2133
12499 14307
92659 3323
65431 91949
95699 70975
57853 36887
99945 51370
7930 43107
21906 45553
91811 45823
94478 86992
82164 44642
23334 83637
83375 5744
19995 38294
20671 58351
16005 73403
25620 86648
70295 20589
50504 92392
55606 64339
57424 62642
35547 15771
...

output:

200001
1 77108 69474 77108 64420 36456 70430 36456 64420 46534 11829 94356 62901 61257 62901 94356 11829 46534 1764 46534 31664 22277 31664 5062 31664 46534 64420 65905 54774 85247 54774 86285 83377 47798 83377 84782 25540 91176 25540 84782 83377 86285 12854 86285 54774 95038 37695 8303 37695 89190 ...

result:

ok Success

Test #65:

score: 0

Accepted

time: 55ms

memory: 26788kb

input:

100000 100000 3
80988 67979
39470 62159
1740 51207
80996 38999
60326 93926
68334 71762
55455 30817
46715 8786
50935 37546
35080 11645
93958 19074
6735 10716
57605 28619
78035 51870
31372 52819
72483 25348
70841 39422
12930 14364
86028 88726
42935 73403
70474 86016
48836 96426
43459 68852
57991 47298...

output:

300001
1 37941 63802 37941 63802 91803 8697 71010 56987 71010 56987 31677 56987 710 2057 710 56987 710 56987 68966 56987 68966 56987 71010 8725 71010 55703 71010 8697 71010 8697 25480 34894 25480 76010 25480 76010 25480 8697 25480 8697 91803 17016 12884 62552 12884 62552 36862 89280 64791 89280 6479...

result:

ok Success

Test #66:

score: 0

Accepted

time: 85ms

memory: 30188kb

input:

100000 100000 10
42508 40371
88753 76711
99724 29244
6537 47569
82014 55231
33263 46498
41642 55268
3223 73289
97839 71028
28363 43019
50367 38714
54049 92574
10364 20590
73025 49867
69123 67464
65140 80049
4071 64419
40553 82230
32742 61666
97373 63185
30735 10747
77295 88126
54267 51633
6625 22478...

output:

1000001
1 5026 72083 5026 72083 5026 72083 5026 72083 5026 72083 76385 72083 76385 72083 76385 72083 76385 72083 76385 72083 5026 76725 5026 76725 5026 76725 5026 76725 5026 76725 40462 76725 40462 76725 40462 76725 40462 76725 40462 76725 5026 31971 5026 31971 5026 31971 5026 31971 5026 31971 27972...

result:

ok Success

Test #67:

score: 0

Accepted

time: 79ms

memory: 30564kb

input:

100000 100000 10
79407 81819
58268 2063
3405 58574
26876 59536
66797 18245
69304 52772
45766 44113
77651 92957
81604 73546
71832 726
27754 57699
80412 6489
73474 97985
48281 43641
38540 38686
21201 25760
62534 58557
52402 49800
34676 167
1116 54756
41716 93723
81342 37560
91601 19884
22117 20242
341...

output:

1000001
1 38422 15498 38422 15498 38422 15498 38422 15498 38422 15498 38422 64008 38422 64008 38422 64008 38422 64008 38422 64008 38422 2928 38422 2928 38422 2928 38422 2928 38422 2928 38422 1 38422 1 38422 1 38422 1 38422 1 55486 31348 55486 31348 55486 31348 55486 31348 55486 31348 81660 32735 816...

result:

ok Success

Test #68:

score: 0

Accepted

time: 54ms

memory: 27244kb

input:

100000 100000 2
80850 5653
88925 39680
85953 69187
2366 84719
69517 15976
92782 71570
87417 76414
3179 51242
12232 62863
72479 63688
95812 34161
7566 10443
67187 53081
54426 98147
45344 62211
37647 22278
60809 14487
37593 37799
93158 38420
71432 45453
64697 30677
35452 67255
41284 5867
74830 95723
3...

output:

200001
1 72317 64868 84958 73658 26061 62171 97666 62171 26061 70405 16857 944 16857 70405 89794 18311 89794 70405 26061 42940 26061 61205 5559 54851 5559 61205 75471 55115 75471 31522 34332 87086 34332 31522 65445 4599 65445 31522 75471 35096 44701 8577 15615 8577 44701 18433 44701 35096 57223 7447...

result:

ok Success

Test #69:

score: 0

Accepted

time: 56ms

memory: 27020kb

input:

100000 100000 3
66988 83389
79322 44868
46411 49931
73335 17127
28068 31264
29210 58136
85056 60957
76068 76361
17288 86064
34459 44199
31735 56398
38276 62810
28785 93521
71982 13854
20635 77739
33136 86236
61292 72776
30616 45236
66171 17221
92334 43921
68144 2348
28528 24021
45388 45654
14762 212...

output:

300001
1 47546 81218 47546 81218 81051 81218 81970 81218 81970 81218 34690 81218 13576 81218 13576 81218 47546 69081 47546 70180 47546 70180 82710 70180 87578 70180 87578 70180 65197 70180 47546 1 47546 1 6918 83039 81653 77197 81653 28167 81653 28167 6139 28167 6139 28167 42275 58219 10052 95439 10...

result:

ok Success

Test #70:

score: 0

Accepted

time: 68ms

memory: 30348kb

input:

100000 100000 10
57969 3439
50733 15352
59092 78866
51883 99553
17245 88110
38500 95434
92316 97060
44375 96503
40953 88784
71411 23187
4058 10582
9797 45250
33546 5533
24250 28396
31502 21565
2503 90522
81244 87955
76980 96896
69379 81562
25036 26808
44965 61473
74995 71919
39175 85540
25774 71136
...

output:

1000001
1 30006 54682 30006 54682 30006 54682 30006 54682 30006 54682 79357 83666 79357 83666 79357 83666 79357 83666 79357 83666 85842 45418 85842 45418 85842 45418 85842 45418 85842 45418 28750 73262 28750 73262 28750 73262 28750 73262 28750 73262 15360 73262 15360 73262 15360 73262 15360 73262 15...

result:

ok Success

Test #71:

score: 0

Accepted

time: 88ms

memory: 30004kb

input:

100000 100000 10
99858 96517
67570 83849
43575 75377
87868 90747
21594 70096
51086 89980
16569 64072
26046 64656
95505 85696
97231 40028
12382 52782
50760 47541
73627 42198
24552 80330
83128 40147
56124 63085
21864 50975
2077 77852
68604 76116
86490 88332
23904 19785
60234 79938
47928 49873
62628 69...

output:

1000001
1 30750 89667 30750 89667 30750 89667 30750 89667 30750 89667 30223 89667 30223 89667 30223 89667 30223 89667 30223 89667 30750 85492 30750 85492 30750 85492 30750 85492 30750 85492 18821 14979 18821 14979 18821 14979 18821 14979 18821 14979 18821 85492 18821 85492 18821 85492 18821 85492 18...

result:

ok Success

Test #72:

score: 0

Accepted

time: 48ms

memory: 26536kb

input:

100000 100000 2
2428 29070
43342 684
64493 26411
14033 48929
93093 23916
16881 30815
13077 41151
54673 83012
84523 76208
35509 63815
31541 43394
25473 6694
88510 66373
94326 75885
40899 62816
21684 50692
30023 55996
74354 66194
62828 95415
78299 42422
12890 56298
15919 68293
57064 65359
70950 46575
...

output:

200001
1 34454 89762 82667 89762 90584 86561 5546 86561 90584 45210 1149 3293 1149 58173 56316 39048 18704 29151 18704 39048 56316 11764 56316 58173 30385 59565 39586 59565 30385 58173 6331 58173 87001 94307 87001 28451 99425 49265 99425 52476 87934 52476 99425 28451 8747 28451 72618 28451 87001 581...

result:

ok Success

Test #73:

score: 0

Accepted

time: 53ms

memory: 26964kb

input:

100000 100000 3
36083 86660
2186 10995
46739 68192
11691 58708
94057 35446
19953 85128
94424 2943
28838 45565
23623 959
79447 39457
78790 7031
43507 71491
9859 45609
94099 46134
14243 90273
64202 60572
21925 39110
22477 5372
71943 49689
32740 95340
91511 64395
42831 55480
93896 78083
33734 86009
483...

output:

300001
1 55515 47256 55515 47256 16153 47256 55515 15553 55515 15553 21477 49116 5857 10635 5857 10635 77031 27999 49771 44355 49771 27999 49771 27999 77031 63501 77031 10635 77031 10635 52300 77303 52300 77303 91560 77303 52300 13062 52300 13062 20482 13062 1509 13062 1509 13062 32221 11656 38338 4...

result:

ok Success

Test #74:

score: 0

Accepted

time: 85ms

memory: 31376kb

input:

100000 100000 10
74114 96561
13527 27276
70678 70644
37167 88442
22274 47418
44272 89095
45353 37171
560 44843
92557 62793
55401 47488
12473 52116
89726 80239
28883 91569
97689 26430
25222 20983
41040 62627
86884 22313
21308 96087
36080 37413
22231 69999
88008 55342
49237 29376
59155 19322
68131 217...

output:

1000001
1 26828 78018 26828 78018 26828 78018 26828 78018 26828 78018 26828 63370 26828 63370 26828 63370 26828 63370 26828 63370 82210 63370 82210 63370 82210 63370 82210 63370 82210 63370 37801 63370 37801 63370 37801 63370 37801 63370 37801 63370 26828 83237 26828 83237 26828 83237 26828 83237 26...

result:

ok Success

Test #75:

score: 0

Accepted

time: 73ms

memory: 30704kb

input:

100000 100000 10
32671 63846
74819 71974
94265 91857
37357 27430
41887 68351
48803 78386
15456 69066
83428 17466
59237 56081
4628 3342
88140 91595
86050 49086
50353 49052
71805 15569
38454 2628
33263 66731
24269 14015
87320 773
88186 62781
47601 18831
86473 34589
13479 53274
73709 97085
70962 97625
...

output:

1000001
1 78220 70055 78220 70055 78220 70055 78220 70055 78220 70055 67374 70055 67374 70055 67374 70055 67374 70055 67374 70055 62576 72726 62576 72726 62576 72726 62576 72726 62576 72726 1678 72726 1678 72726 1678 72726 1678 72726 1678 72726 80897 72726 80897 72726 80897 72726 80897 72726 80897 7...

result:

ok Success

Test #76:

score: 0

Accepted

time: 22ms

memory: 19348kb

input:

10000 100000 2
8142 2235
1161 6866
9026 4439
2350 598
5683 4108
3187 9693
1263 4998
2683 1891
210 1372
609 4446
7474 6391
1576 8731
2980 1508
8604 6509
7085 1943
5716 4557
7649 3866
2031 3993
3910 9274
4921 4825
4799 4118
8211 6787
6231 6885
7449 5868
6766 4656
4491 8459
6356 4380
5608 7687
7353 795...

output:

200001
1 155 8349 7512 3337 168 3205 1 3205 3880 946 1759 8139 8141 8166 7908 5236 8032 3185 8736 2641 8329 1000 1 1000 3474 5963 4624 8656 6519 4712 5373 6615 723 9035 4340 9927 2179 3798 2525 7635 588 8004 274 5966 4799 4118 1863 5305 1834 962 8993 4402 50 6230 5832 433 56 1896 8451 997 8790 4967 ...

result:

ok Success

Test #77:

score: 0

Accepted

time: 29ms

memory: 19804kb

input:

10000 100000 3
596 7033
4582 1
5095 6333
3127 9501
2906 1
2578 6437
7634 7749
3003 886
3869 6574
45 6981
9223 1560
5691 8661
1178 1
2755 537
4481 4811
7483 829
3702 6653
1021 6026
8177 2729
9147 7076
4659 5373
6299 4449
6674 1476
6339 1640
7429 1
9643 8519
5817 1194
4684 5073
6741 129
831 678
7344 3...

output:

300001
1 4582 493 4582 493 5914 7352 1 7352 1 7352 1073 7516 1096 1379 1096 1379 4935 5537 1046 277 1046 277 3318 2613 1791 8579 1791 8579 1806 7982 907 7109 907 7109 3197 8398 4084 3748 4084 3748 2737 183 1 183 1 183 2606 4673 5786 1351 5786 1351 1457 2162 4600 9045 4600 9045 7388 4836 4308 7999 43...

result:

ok Success

Test #78:

score: 0

Accepted

time: 62ms

memory: 23824kb

input:

10000 100000 10
150 945
688 6591
7033 7003
4711 9867
5303 4962
7326 7816
5765 9401
825 2168
8541 9452
5241 2357
6908 4844
4056 3990
5455 8225
2822 8196
2683 1957
9001 7983
2499 5897
1732 13
3918 4068
1629 1181
8722 8869
4418 6586
7951 3338
5486 1
4726 6343
8512 3267
9357 1
2973 9173
2449 2600
6482 9...

output:

1000001
1 5486 4859 5486 4859 5486 4859 5486 4859 5486 4859 5556 1814 5556 1814 5556 1814 5556 1814 5556 1814 8309 3502 8309 3502 8309 3502 8309 3502 8309 3502 457 2196 457 2196 457 2196 457 2196 457 2196 3451 4257 3451 4257 3451 4257 3451 4257 3451 4257 7201 750 7201 750 7201 750 7201 750 7201 750 ...

result:

ok Success

Test #79:

score: 0

Accepted

time: 65ms

memory: 22636kb

input:

10000 100000 10
4884 2287
4145 1176
6921 9149
7296 7114
5560 4732
5841 1666
802 1976
3548 8810
379 1002
7553 8518
984 9640
9607 6409
6485 1
9448 2670
2097 3972
8328 2505
7533 3220
4803 5563
9453 8026
5286 6259
9401 1
3445 8309
85 3379
2073 4793
5387 2388
6808 6154
8105 2375
939 1396
2145 1
5390 4498...

output:

1000001
1 6485 4938 6485 4938 6485 4938 6485 4938 6485 4938 1 4938 1 4938 1 4938 1 4938 1 4938 8017 6198 8017 6198 8017 6198 8017 6198 8017 6198 8355 3746 8355 3746 8355 3746 8355 3746 8355 3746 226 1 226 1 226 1 226 1 226 1 226 8662 226 8662 226 8662 226 8662 226 8662 838 4084 838 4084 838 4084 838...

result:

ok Success

Test #80:

score: 0

Accepted

time: 28ms

memory: 19732kb

input:

10000 100000 2
197 3496
4994 7177
5159 7846
6943 9038
2386 9588
5851 1
8451 5084
6721 2106
2592 4443
5881 1767
6319 8351
1898 7467
9995 1
9462 1
827 8650
2538 1
6474 7436
2416 6378
2018 2325
6660 8850
6783 6028
5339 8295
8796 1848
7129 2820
2584 3840
8500 2459
8627 7426
7825 9038
7321 4474
6507 7883...

output:

200001
1 5851 2149 306 8048 4056 646 8681 5720 9707 6572 7870 8583 1 8583 5735 4133 6844 2637 2199 9948 4315 2137 1884 4942 5999 642 4275 2766 1 2766 6418 950 490 1603 5647 7291 9034 5250 9168 1257 5580 7506 2423 4934 7338 4158 547 8969 4200 5843 7049 7597 1291 2450 9686 138 4973 8370 7015 3946 6068...

result:

ok Success

Test #81:

score: 0

Accepted

time: 33ms

memory: 19764kb

input:

10000 100000 3
9627 6721
4397 4219
1135 2666
6042 50
8755 257
4532 536
3875 4336
3735 4547
2763 3916
2075 9348
5065 8449
6426 7771
3368 4600
5148 4367
1452 5986
8526 8247
4605 1
4606 798
373 5202
7526 1
6946 5704
3921 5795
3755 4701
9398 845
8577 3335
902 8921
2134 1
2760 1207
5837 3627
4073 4466
68...

output:

300001
1 4605 1698 4605 1698 7262 6124 1 6124 1 6124 6312 3647 1927 6866 1927 6866 8897 4670 9967 6805 9967 6805 2559 8690 1 8690 1 8690 7125 3951 5897 6107 5897 6107 1490 8696 1 8696 1 8696 2425 5568 9727 1 9727 8461 9727 8461 1275 4778 1275 4778 1 4778 7094 8687 7094 8687 7776 3180 9655 9016 9655 ...

result:

ok Success

Test #82:

score: 0

Accepted

time: 68ms

memory: 22580kb

input:

10000 100000 10
85 7783
3581 3944
6378 3955
6208 2822
8132 128
9869 3391
9280 5323
292 3024
5578 8292
8395 4874
2130 1
4335 6449
3107 4588
5174 2014
1756 1426
7760 7765
1615 1
9900 1721
7510 7515
3805 4481
1303 7117
6346 1
674 6114
9396 1
7304 8021
3764 5433
889 9277
1924 1008
502 9903
3599 2767
961...

output:

1000001
1 2130 3591 2130 3591 2130 3591 2130 3591 2130 3591 1 3591 1 3591 1 3591 1 3591 1 3591 4851 640 4851 640 4851 640 4851 640 4851 640 1 640 1 640 1 640 1 640 1 640 8798 2212 8798 2212 8798 2212 8798 2212 8798 2212 5979 5851 5979 5851 5979 5851 5979 5851 5979 5851 2216 1275 2216 1275 2216 1275 ...

result:

ok Success

Test #83:

score: 0

Accepted

time: 64ms

memory: 23020kb

input:

10000 100000 10
1294 1
1346 3612
6497 765
9961 426
7165 761
6484 4898
9595 9900
9610 357
627 5965
3667 7886
674 2333
3963 4229
4209 6211
2347 7106
8076 5295
206 1
2487 1
7902 9387
7818 181
839 7920
8366 6586
4191 2660
613 4245
6116 9946
5734 1
374 6733
1256 4482
1777 1
6820 3101
9139 1
383 658
7077 ...

output:

1000001
1 1294 6355 1294 6355 1294 6355 1294 6355 1294 6355 1904 8687 1904 8687 1904 8687 1904 8687 1904 8687 1033 1544 1033 1544 1033 1544 1033 1544 1033 1544 2770 970 2770 970 2770 970 2770 970 2770 970 1 970 1 970 1 970 1 970 1 970 7808 7334 7808 7334 7808 7334 7808 7334 7808 7334 6121 5053 6121 ...

result:

ok Success

Test #84:

score: 0

Accepted

time: 28ms

memory: 20064kb

input:

10000 100000 2
8723 2631
3037 9747
7764 4269
1971 5652
823 2096
563 8889
4711 7977
3294 958
9178 3582
5107 1688
7285 6109
4222 5372
2892 8150
7338 5915
4839 9343
5776 4882
3080 1
9323 8895
5385 5627
3858 879
5513 8399
6653 5225
4631 1258
1677 5352
7393 6796
2634 7704
2362 6086
2357 6279
8359 9717
31...

output:

200001
1 3080 5082 1 5082 345 7045 5575 8517 5493 1659 2015 3687 6130 8973 8998 7685 4565 2512 2746 1978 3123 1 3123 6313 6269 8717 4160 453 5572 3471 7687 5075 1120 3257 3267 3829 4013 1 4013 5006 9266 9453 1 9453 7080 8397 6516 8587 9535 6334 2194 2649 8824 8283 4847 4229 2808 708 305 3355 6153 1 ...

result:

ok Success

Test #85:

score: 0

Accepted

time: 33ms

memory: 20588kb

input:

10000 100000 3
3547 5360
458 3010
9005 8222
3922 1590
5663 1
5448 933
8404 6277
5460 127
5184 3564
5859 8528
8059 5392
9742 1133
260 8806
8487 6795
659 9657
6466 5592
2533 8204
8217 6858
8385 5664
6966 7747
179 7550
6429 4928
590 2939
4253 2153
4258 8555
6855 423
7722 3455
4845 8697
8865 8106
5606 2...

output:

300001
1 5663 7324 5663 7324 7839 7277 6732 6502 6732 6502 3094 8935 2578 639 2578 639 6268 1 6268 7636 6268 7636 9437 7420 2876 5080 2876 5080 9481 6293 1 6293 1 6293 1175 625 3583 129 3583 129 301 210 1 210 1 210 1378 2876 1378 5709 1378 5709 7416 6796 9864 3370 9864 3370 9400 7475 8235 2215 8235 ...

result:

ok Success

Test #86:

score: 0

Accepted

time: 56ms

memory: 22276kb

input:

10000 100000 10
7409 3950
5275 280
8240 4054
8667 2451
6697 3108
6019 6319
3674 6518
1013 1
4408 9751
9287 2001
9218 4734
2801 3143
7190 8455
4062 3137
1884 2764
7512 5793
4994 9531
3559 2371
5573 195
2599 6879
4512 290
2878 4500
3787 5892
3232 4540
3608 1
3537 8844
4762 5671
8322 1
1613 1356
9490 8...

output:

1000001
1 1013 7594 1013 7594 1013 7594 1013 7594 1013 7594 2865 8015 2865 8015 2865 8015 2865 8015 2865 8015 4470 6068 4470 6068 4470 6068 4470 6068 4470 6068 9558 5804 9558 5804 9558 5804 9558 5804 9558 5804 4541 8119 4541 8119 4541 8119 4541 8119 4541 8119 8867 3586 8867 3586 8867 3586 8867 3586 ...

result:

ok Success

Test #87:

score: 0

Accepted

time: 61ms

memory: 23076kb

input:

10000 100000 10
5532 6010
9039 1136
1968 2928
6222 5437
8694 7402
7661 1519
805 1
676 5827
9449 5007
7323 9501
7122 5244
1719 6502
4885 4005
1952 7909
5055 9185
489 1
5839 1
9495 157
6625 3610
1879 7681
3250 2751
6274 1
1657 9999
2100 7765
2184 9057
1179 4472
6015 6965
8596 2613
9644 8283
3181 8726
...

output:

1000001
1 805 9963 805 9963 805 9963 805 9963 805 9963 3255 2778 3255 2778 3255 2778 3255 2778 3255 2778 3475 3643 3475 3643 3475 3643 3475 3643 3475 3643 8897 6551 8897 6551 8897 6551 8897 6551 8897 6551 3996 9594 3996 9594 3996 9594 3996 9594 3996 9594 5970 5695 5970 5695 5970 5695 5970 5695 5970 ...

result:

ok Success

Test #88:

score: 0

Accepted

time: 24ms

memory: 16856kb

input:

1000 100000 2
236 859
218 15
151 696
693 200
123 315
394 119
315 775
418 347
347 997
416 865
385 249
481 444
606 509
713 934
828 229
975 812
866 237
380 790
781 568
256 575
570 108
708 967
994 563
584 994
190 66
973 429
474 847
480 617
553 255
861 950
524 278
468 769
31 543
878 297
680 8
267 908
991...

output:

200001
1 972 395 552 738 630 388 335 531 346 506 813 598 953 497 112 95 230 400 445 696 151 591 52 890 441 937 326 448 493 1 493 281 675 71 160 553 255 212 516 299 286 170 441 170 962 734 863 169 837 819 905 742 443 45 167 409 919 27 83 930 688 57 544 227 849 950 861 775 315 123 772 492 446 8 680 14...

result:

ok Success

Test #89:

score: 0

Accepted

time: 23ms

memory: 17440kb

input:

1000 100000 3
117 819
998 317
899 107
754 475
160 573
969 652
954 604
33 37
767 341
272 861
234 90
556 215
835 1
572 400
836 878
259 471
117 635
140 410
112 7
925 723
589 29
847 791
351 684
866 385
880 852
112 691
818 405
884 707
652 386
914 378
443 306
281 547
645 817
185 906
157 187
525 341
590 73...

output:

300001
1 835 970 835 970 41 589 29 944 29 944 285 283 419 46 419 46 454 201 157 187 157 187 120 17 282 146 282 146 278 740 698 519 698 519 113 878 836 150 836 150 117 819 460 890 460 890 595 330 540 198 540 198 912 160 573 177 573 177 753 203 316 83 316 83 415 411 868 919 868 919 670 626 521 773 521...

result:

ok Success

Test #90:

score: 0

Accepted

time: 56ms

memory: 20608kb

input:

1000 100000 10
154 893
463 349
304 1
103 689
534 54
964 667
307 389
768 577
323 216
636 867
487 735
498 22
521 155
365 661
8 38
719 743
633 474
868 954
476 985
250 13
864 45
337 314
8 712
981 896
566 757
284 211
813 951
660 940
932 462
589 535
390 573
973 370
14 42
272 128
414 656
535 227
314 117
55...

output:

1000001
1 304 760 304 760 304 760 304 760 304 760 232 307 232 307 232 307 232 307 232 307 389 222 389 222 389 222 389 222 389 222 691 147 691 147 691 147 691 147 691 147 434 616 434 616 434 616 434 616 434 616 685 458 685 458 685 458 685 458 685 458 981 896 981 896 981 896 981 896 981 896 326 344 32...

result:

ok Success

Test #91:

score: 0

Accepted

time: 55ms

memory: 21524kb

input:

1000 100000 10
147 1000
137 456
995 801
29 4
277 244
130 670
409 917
664 195
366 397
169 621
140 235
309 118
579 515
211 941
992 608
581 446
345 679
52 817
69 374
77 236
744 305
855 624
687 499
851 77
230 576
374 570
488 677
142 612
50 110
498 692
492 232
361 581
68 357
901 281
920 641
578 482
453 6...

output:

1000001
1 855 624 855 624 855 624 855 624 855 624 986 3 986 3 986 3 986 3 986 3 298 322 298 322 298 322 298 322 298 322 996 940 996 940 996 940 996 940 996 940 312 561 312 561 312 561 312 561 312 561 696 596 696 596 696 596 696 596 696 596 644 591 644 591 644 591 644 591 644 591 523 191 523 191 523 ...

result:

ok Success

Test #92:

score: 0

Accepted

time: 15ms

memory: 16916kb

input:

1000 100000 2
94 292
22 977
548 441
410 759
641 486
665 899
831 317
395 719
805 142
526 396
976 572
496 277
469 179
551 66
426 446
449 559
824 699
140 529
372 375
76 608
925 245
948 979
519 580
93 757
834 406
979 729
680 18
689 772
864 12
793 651
850 58
762 503
505 179
113 561
958 945
320 609
524 40...

output:

200001
1 109 918 580 519 767 68 694 913 350 85 651 793 518 596 106 716 390 94 292 939 277 496 42 388 272 530 731 913 731 765 752 577 338 591 580 591 33 750 246 463 6 660 172 346 366 383 15 891 517 391 1 391 985 915 374 335 963 140 529 992 905 818 906 212 839 321 72 735 865 493 49 501 415 302 894 502...

result:

ok Success

Test #93:

score: 0

Accepted

time: 27ms

memory: 17908kb

input:

1000 100000 3
889 847
548 91
424 54
534 322
688 458
215 311
478 203
26 728
583 419
85 318
171 176
236 454
338 165
802 400
393 769
321 859
191 66
854 1000
340 922
219 212
38 594
708 665
957 646
660 778
380 699
150 198
903 291
540 305
253 295
162 956
369 968
10 121
70 674
72 426
314 19
130 635
664 166...

output:

300001
1 358 414 358 414 46 776 911 946 911 946 716 991 955 308 955 308 644 468 236 454 236 454 601 891 455 284 455 284 889 847 149 705 149 705 415 944 518 228 518 228 565 514 464 673 464 673 759 665 708 525 708 525 767 750 198 150 198 150 409 837 651 495 651 495 580 497 827 245 827 245 416 329 721 ...

result:

ok Success

Test #94:

score: 0

Accepted

time: 58ms

memory: 19816kb

input:

1000 100000 10
288 381
14 310
371 95
209 714
709 196
300 123
574 259
183 828
133 702
378 463
546 256
905 291
128 939
983 92
697 201
32 621
643 973
878 148
976 146
807 614
41 700
657 471
357 12
901 853
62 255
301 517
129 668
65 40
941 998
998 803
912 390
306 986
490 880
95 222
721 577
3 39
210 88
71 ...

output:

1000001
1 959 396 959 396 959 396 959 396 959 396 6 103 6 103 6 103 6 103 6 103 737 985 737 985 737 985 737 985 737 985 658 282 658 282 658 282 658 282 658 282 653 583 653 583 653 583 653 583 653 583 5 260 5 260 5 260 5 260 5 260 560 879 560 879 560 879 560 879 560 879 873 628 873 628 873 628 873 62...

result:

ok Success

Test #95:

score: 0

Accepted

time: 54ms

memory: 20956kb

input:

1000 100000 10
507 869
525 813
796 972
328 998
835 48
778 700
164 787
266 905
674 622
903 152
875 828
503 451
257 242
521 300
662 578
108 261
985 445
691 697
691 209
558 188
513 217
635 296
617 947
983 651
891 772
794 382
438 429
341 787
386 489
531 988
892 334
563 515
687 175
103 593
257 815
639 45...

output:

1000001
1 523 721 523 721 523 721 523 721 523 721 347 97 347 97 347 97 347 97 347 97 142 52 142 52 142 52 142 52 142 52 620 684 620 684 620 684 620 684 620 684 626 239 626 239 626 239 626 239 626 239 590 379 590 379 590 379 590 379 590 379 355 957 355 957 355 957 355 957 355 957 488 515 488 515 488 ...

result:

ok Success

Test #96:

score: 0

Accepted

time: 15ms

memory: 17040kb

input:

1000 100000 2
692 158
423 28
410 832
423 300
581 397
888 522
589 952
254 399
286 803
123 804
942 184
555 970
549 573
552 283
954 133
136 1
304 768
926 332
448 278
862 618
572 41
446 683
868 681
13 854
79 200
341 690
185 899
390 878
227 687
661 708
227 468
356 355
201 804
569 970
380 818
383 890
199 ...

output:

200001
1 136 252 879 253 123 804 201 128 347 970 555 102 100 137 176 233 878 390 414 490 1 490 629 807 107 1 107 923 489 514 766 665 896 703 885 427 640 769 522 888 586 595 172 218 755 458 906 6 301 531 611 648 274 399 254 798 611 798 61 815 267 352 460 857 882 219 131 759 101 757 349 421 7 535 989 ...

result:

ok Success

Test #97:

score: 0

Accepted

time: 23ms

memory: 17972kb

input:

1000 100000 3
112 515
757 731
641 129
625 552
943 354
837 865
16 950
555 88
536 36
512 375
151 388
37 136
156 719
680 468
504 392
752 326
438 880
301 875
859 747
497 45
2 864
275 464
380 204
592 40
686 320
978 915
677 400
563 2
788 82
108 118
179 733
822 723
408 287
691 871
240 228
842 179
327 126
6...

output:

300001
1 327 126 327 126 861 401 759 175 759 175 259 131 755 539 755 539 557 561 386 114 386 114 918 648 526 644 526 644 415 760 628 799 628 799 247 888 144 673 144 673 649 83 409 884 409 884 448 7 67 846 67 846 693 181 267 656 267 656 371 855 932 314 932 314 568 218 301 875 301 875 556 139 443 609 ...

result:

ok Success

Test #98:

score: 0

Accepted

time: 58ms

memory: 23764kb

input:

1000 100000 10
86 848
797 982
129 191
649 233
622 836
793 873
40 629
123 213
149 781
292 215
42 277
842 661
522 774
201 578
932 494
893 617
956 839
583 879
10 46
648 167
851 405
832 925
134 943
693 576
611 843
107 859
998 477
307 566
536 572
305 190
698 740
383 807
809 80
135 660
324 433
69 984
475 ...

output:

1000001
1 82 548 82 548 82 548 82 548 82 548 351 190 351 190 351 190 351 190 351 190 305 5 305 5 305 5 305 5 305 5 428 310 428 310 428 310 428 310 428 310 709 463 709 463 709 463 709 463 709 463 156 898 156 898 156 898 156 898 156 898 981 694 981 694 981 694 981 694 981 694 189 842 189 842 189 842 1...

result:

ok Success

Test #99:

score: 0

Accepted

time: 54ms

memory: 21604kb

input:

1000 100000 10
43 843
845 247
659 877
527 636
174 454
977 460
37 215
689 914
766 491
915 945
518 246
990 1
195 68
591 822
737 143
567 184
542 976
187 711
614 583
130 937
141 738
577 521
226 291
529 822
171 50
851 175
686 790
676 515
306 311
617 614
623 217
247 726
372 86
301 503
109 262
84 404
588 8...

output:

1000001
1 990 622 990 622 990 622 990 622 990 622 491 766 491 766 491 766 491 766 491 766 675 582 675 582 675 582 675 582 675 582 171 50 171 50 171 50 171 50 171 50 649 223 649 223 649 223 649 223 649 223 470 763 470 763 470 763 470 763 470 763 65 194 65 194 65 194 65 194 65 194 521 577 521 577 521 ...

result:

ok Success

Test #100:

score: 0

Accepted

time: 50ms

memory: 19612kb

input:

10000 100000 5
4022 9081
9493 1
574 618
8332 1728
9596 5349
9611 5509
2922 1
6871 9164
9092 4647
9153 5430
5772 9007
7642 5897
9545 3546
991 7920
2990 3768
8788 2779
7533 6920
4539 4458
3548 6492
5392 5130
655 4597
9992 3977
5354 6417
3564 1399
2985 1
4753 1400
1806 5746
2247 2232
7036 1
6758 8
6205...

output:

500001
1 9493 9996 9493 9996 9493 9996 5147 9535 5147 9535 8955 8349 8955 8349 8955 8349 1114 6765 1114 6765 6625 2734 6625 2734 6625 2734 2060 4465 2060 4465 367 2992 367 2992 367 2992 1151 1652 1151 1652 2412 9257 2412 9257 2412 9257 992 6114 992 6114 870 7393 870 7393 870 7393 537 3348 537 3348 2...

result:

ok Success

Test #101:

score: 0

Accepted

time: 69ms

memory: 28320kb

input:

50000 100000 6
49703 41089
47787 31876
22605 30664
37494 1
28334 1
6948 1
41726 8184
38933 1
43316 11588
7783 1
49054 1
47307 34776
49343 31586
27955 1
17996 14357
42827 1
42765 43699
46710 1
40834 22354
34320 22778
36825 13164
7603 18570
34363 42660
17854 39745
17096 1
19987 6457
37628 1
37531 1
31...

output:

600001
1 37494 23848 37494 23848 37494 23848 1 23848 1 23848 1 23848 48889 16914 48889 16914 48889 16914 15783 10929 15783 10929 15783 10929 18028 42549 18028 42549 18028 42549 32305 15066 32305 15066 32305 15066 1 15066 1 15066 1 15066 13829 1 13829 1 13829 1 13829 48492 13829 48492 13829 48492 319...

result:

ok Success

Test #102:

score: 0

Accepted

time: 53ms

memory: 26216kb

input:

30000 100000 7
28475 398
4153 18627
8832 15636
8802 7431
10110 1
11056 187
3396 1
10562 9029
19424 1
4965 22918
23732 1
9262 18131
2588 1
23004 1
10548 6198
18763 26992
19072 1
17987 7523
12299 2970
15266 13068
3839 1
13653 4225
955 24492
2555 12181
21322 24009
11292 1
795 1
7780 1
20779 1
13158 1
2...

output:

700001
1 10110 10553 10110 10553 10110 10553 10110 10553 3503 11306 3503 11306 3503 11306 10555 4674 10555 4674 10555 4674 10555 4674 27917 15724 27917 15724 27917 15724 7435 1 7435 1 7435 1 7435 21122 7435 21122 7435 21122 7435 21122 1904 26461 1904 26461 1904 26461 1904 26461 22273 19840 22273 198...

result:

ok Success

Test #103:

score: 0

Accepted

time: 81ms

memory: 31472kb

input:

100000 100000 10
45984 98160
7379 51593
98986 9690
53309 11249
9448 64626
72660 35271
89851 87140
94958 75361
92567 87475
78927 17649
28620 42016
81729 52783
76778 44767
38654 90398
71208 70085
6532 70508
71456 93928
76430 78973
56549 3238
54013 18905
84291 69985
86197 22190
33787 99117
4761 17123
5...

output:

1000001
1 19341 6699 19341 6699 19341 6699 19341 6699 19341 6699 23384 6699 23384 6699 23384 6699 23384 6699 23384 6699 19341 42147 19341 42147 19341 42147 19341 42147 19341 42147 56601 9936 56601 9936 56601 9936 56601 9936 56601 9936 56601 67380 56601 67380 56601 67380 56601 67380 56601 67380 56601...

result:

ok Success

Test #104:

score: 0

Accepted

time: 50ms

memory: 23648kb

input:

10000 100000 8
3756 5950
1221 2395
6963 6655
7272 3135
7157 3125
7025 2747
4537 3620
910 4430
5815 1286
258 6761
2883 1
9533 1558
5812 1
2564 6680
5981 8593
7934 5572
483 8113
4507 1
6941 4006
2726 402
3032 712
3732 1
4466 4741
6506 746
326 977
8586 2257
2897 1412
8627 8574
1693 4928
2612 2541
6751 ...

output:

800001
1 2883 8313 2883 8313 2883 8313 2883 8313 8 5389 8 5389 8 5389 8 5389 4944 5439 4944 5439 4944 5439 4944 5439 1 5439 1 5439 1 5439 1 5439 3606 1 3606 1 3606 1 3606 1 3606 9508 3606 9508 3606 9508 3606 9508 2994 8233 2994 8233 2994 8233 2994 8233 3986 4260 3986 4260 3986 4260 3986 4260 9694 84...

result:

ok Success

Test #105:

score: 0

Accepted

time: 76ms

memory: 29396kb

input:

50000 100000 9
38941 844
30026 4110
12450 1
49346 1
10213 28776
8115 8946
27261 1
21661 21173
29524 49983
41778 1
47315 25644
39334 15037
40856 36277
42576 23851
786 19906
4544 48590
29364 46645
16830 22455
13382 46461
15680 48828
6965 1
29632 21872
22338 1
21847 1
35764 10554
3338 3482
5917 49524
3...

output:

900001
1 12450 42097 12450 42097 12450 42097 12450 42097 12450 42097 35062 20199 35062 20199 35062 20199 35062 20199 48982 41720 48982 41720 48982 41720 48982 41720 48982 41720 32044 14666 32044 14666 32044 14666 32044 14666 33046 1 33046 1 33046 1 33046 1 33046 9335 33046 9335 33046 9335 33046 9335...

result:

ok Success

Test #106:

score: 0

Accepted

time: 58ms

memory: 21380kb

input:

2000 100000 10
747 168
359 683
1260 754
364 1409
197 846
1422 1348
786 1542
1188 1
472 891
1541 139
1307 1488
251 877
980 128
1003 784
677 1649
1479 1968
893 85
1496 1925
1802 769
752 343
1735 217
852 487
981 16
606 1968
193 1616
1277 255
791 1503
1211 522
337 312
453 1009
964 143
775 134
880 1155
1...

output:

1000001
1 1188 1936 1188 1936 1188 1936 1188 1936 1188 1936 1191 332 1191 332 1191 332 1191 332 1191 332 1813 1122 1813 1122 1813 1122 1813 1122 1813 1122 1707 600 1707 600 1707 600 1707 600 1707 600 707 1218 707 1218 707 1218 707 1218 707 1218 925 1262 925 1262 925 1262 925 1262 925 1262 945 285 94...

result:

ok Success

Test #107:

score: 0

Accepted

time: 84ms

memory: 30408kb

input:

90000 100000 10
48451 904
4346 32625
52932 19268
25879 51221
18938 56169
5167 64285
25889 88502
54144 46575
39452 57662
56240 54871
48186 19561
69512 50871
31004 59824
35730 71313
5790 42277
56841 1
68607 1
32070 62071
17683 13806
81190 74436
73550 86313
22374 36778
26814 15435
22937 34330
2842 8644...

output:

1000001
1 56841 40646 56841 40646 56841 40646 56841 40646 56841 40646 75776 17918 75776 17918 75776 17918 75776 17918 75776 17918 21015 17918 21015 17918 21015 17918 21015 17918 21015 17918 75776 85224 75776 85224 75776 85224 75776 85224 75776 85224 5000 85224 5000 85224 5000 85224 5000 85224 5000 8...

result:

ok Success

Test #108:

score: 0

Accepted

time: 1ms

memory: 7948kb

input:

2 1 10
2 1

output:

11
1 2 1 2 1 2 1 2 1 2 1

result:

ok Success

Test #109:

score: 0

Accepted

time: 1ms

memory: 5612kb

input:

2 1 1
1 2

output:

2
1 2

result:

ok Success