#include <cstdio>
#include <queue>
#include <iostream>

using namespace std;

int main(){
    int T;
    scanf("%d",&T);
    while(T --){
        int n,m;
        scanf("%d%d",&m,&n);
        printf("%d %d\n",m,(n + 1) / 2);

        priority_queue<int> down;
        priority_queue<int, vector<int>,greater<int> > up;

        int cnt = 0;
        for(int i = 1; i <= n; i ++){
            int x;
            scanf("%d",&x);
            if(down.empty() || x <= down.top())down.push(x);
            else up.push(x);

            if(down.size() > up.size() + 1) up.push(down.top()),down.pop();
            if(up.size() > down.size()) down.push(up.top()),up.pop();

            if(i % 2){
                printf("%d ",down.top());
                if(++ cnt % 10 == 0)puts("");
            }


        }
        if(cnt % 10)puts("");
    }
    return 0;
} 

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

const int N = 2e5+7,M = 18;
int f[N][M],w[N],n,m;
void init(){
    for(int j = 0; j <= M; j ++){
        for(int i = 1; i + (1 << j) - 1 <= n; i ++){
            if(!j)f[i][j] = w[i];
            else f[i][j] = max(f[i][j - 1],f[i + (1 << j - 1)][j - 1]);
        }
    }
}

int query(int l,int r){
    int len = r - l + 1;
    int k = log(len) / log(2);
    return max(f[l][k],f[r - (1 << k) + 1][k]);
}

int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; i ++)scanf("%d",&w[i]);
    init();
    scanf("%d",&m);
    for(int i = 1; i <= m; i ++){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",query(l,r));
    }

}

#include <iostream>
using namespace std;

#define LL long long

int gcd(int a,int b){
    return b ? gcd(b, a % b) : a;
}
LL qmi(LL a,LL b,LL p){
    int t = b - 2;
    LL res = 1;
    while(t){
        if(t & 1)res = res * a % p;
        a = a * a % p;
        t >>= 1;
    }
    return res;
}
int main(){
    int n;
    cin >> n;
    while(n --){
        int ai,pi;
        cin >> ai >> pi;
        if(ai % pi)cout << qmi(ai,pi,pi) << endl;
        else cout << "impossible" << endl;
    }
    return 0;
}

#include <iostream>
using namespace std;
typedef long long LL;

int gcd(int a,int b){
    return b ? gcd(b, a % b) : a;
}

LL C(int n)//c(3,n)
{
    return (LL)n * (n - 1) * (n - 2) / 6;
}

int main(){
    int n,m;
    cin >> n >> m;
    n ++,m ++;
    LL res = C(n * m) - (LL)n * C(m) - (LL)m * C(n);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++){
            res -= 2ll * (gcd(i,j) - 1) * (n - i) * (m - j);
        }
    cout << res << endl;
}

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 150;//150位

int k,x;
int f[1000][100][N];

int qmi(int a,int b,int p){
    int res = 1 % p;
    while(b){
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

void add(int c[],int a[],int b[]){
    for(int i = 0,t = 0; i < N; i ++){
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
}
int main(){
    cin >> k >> x;
    int n = qmi(x % 1000,x,1000);

    for(int i = 0; i < n; i ++)
        for(int j = 0; j <= i && j < k; j ++)
            if(!j)f[i][j][0] = 1;
            else add(f[i][j],f[i - 1][j - 1] , f[i - 1][j]);

    int *g = f[n - 1][k - 1];        
    int i = N - 1;
    while(!g[i]) i --;
    while(i >= 0)cout << g[i--];
}

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 1e5 + 7,mod = 5000011;
int n,k;
int f[N],s[N];

int main()
{
cin >> n >> k;

f[0] = s[0] = 1;
for(int i = 1; i <= n; i ++){
    f[i] = s[max(i - k - 1,0)];
    s[i] = (s[i - 1] + f[i]) % mod;
}
cout << s[n] << endl;
return 0;

}

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 10;

int n;
int A[N], B[N];

void exgcd(LL a, LL b, LL &x, LL &y)
{
    if (!b) x = 1, y = 0;
    else
    {
        exgcd(b, a % b, y, x);
        y -= a / b * x;
    }
}

int main()
{
    scanf("%d", &n);

    LL M = 1;
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d%d", &A[i], &B[i]);
        M *= A[i];
    }

    LL res = 0;
    for (int i = 0; i < n; i ++ )
    {
        LL Mi = M / A[i];
        LL ti, x;
        exgcd(Mi, A[i], ti, x);
        res += B[i] * Mi * ti;
    }

    cout << (res % M + M) % M << endl;

    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long LL;


LL qmul(LL a,LL k,LL b){
    LL res = 0;
    while(k){
        if(k & 1) res = (res + a) % b;
        a = (a + a) % b;
        k >>= 1;
    }
    return res;
}

LL qmi(LL a,LL k,LL b){
    LL res = 1 % b;
    while(k){
        if(k & 1) res = qmul(res,a,b);
        a = qmul(a,a,b);
        k >>= 1;
    }
    return res;
}
LL get_euler(LL C){
    LL res =  C;
    for(LL i = 2; i <= C / i; i ++){
        if(C % i == 0){
            while(C % i == 0) C /= i;
            res = res / i * (i - 1) ;//防止溢出先除后乘
        }
    }
    if(C > 1) res = res / C * (C - 1);
    return res;
}
int main(){
    int T = 1;
    LL L;
    while(cin >> L,L){
        int d = 1;
        while(L % (d * 2) == 0 && d * 2 <= 8)d *= 2;
        LL C = 9 * L / d;
        LL phi = get_euler(C);

        LL res =  1e18;
        if(C % 2 == 0 || C % 5 == 0)res = 0;

        for(LL d = 1; d * d <= phi; d ++)
            if(phi % d == 0)
            {
                if(qmi(10,d,C) == 1)res = min(res,d);
                if(qmi(10,phi / d,C) == 1)res = min(res,phi / d);
            }


        printf("Case %d: %lld\n",T ++,res);
    }
    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int exgcd(LL a,LL b,LL &x,LL &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b,a % b,y,x);
    y -= a / b * x;
    return d;
}
int main(){
    LL a,b,m,n,L;
    cin >> a >> b >> m >> n >> L;

    LL x,y;
    LL d = exgcd(m - n, L ,x,y);

    if((b - a) % d)puts("Impossible");
    else{
        x *= (b - a) / d;
        LL t = abs(L / d);
        cout << (x % t + t) % t << endl;
    }

    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b,a % b, y, x);
    y -= a / b * x;

    return d;
}
int main(){
    int a,b,x,y;
    cin >> a >> b;
    exgcd(a,b,x,y);
    cout << (x % b + b) % b << endl;
    return 0;
}