/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 你需要返回m个指针，第i个指针指向一条链，表示第i个问题的答案
     * @param root TreeNode类 指向链表树的根
     * @param b int整型vector 表示每个问题是什么
     * @return ListNode类vector
     */
    vector<ListNode*> solve(TreeNode* root, vector<int>& b) {
        // write code here
        vector<int> tmp[1002];
        vector<int> u;
        function<void(TreeNode*)> dfs = [&](TreeNode* cur) {
            u.push_back(cur->val);
            tmp[cur->val] = u;
            if (cur->left) dfs(cur->left), u.pop_back();
            if (cur->right) dfs(cur->right), u.pop_back();
        };
        dfs(root);
        vector<ListNode*> ret;
        for (int i = 0; i < (int)b.size(); i++) {
            ListNode* head = new ListNode(-1);
            ListNode* f = head;
            for (int u : tmp[b[i]]) {
                head->next = new ListNode(u);
                head = head->next;
            }
            ret.push_back(f->next);
        }
        return ret;
    }
};
---------------------------------------------------------------------------------------------

#include <bits/stdc++.h>

using namespace std;

int main() {
    int tt;
    scanf("%d", &tt);
    while (tt--) {
        int nn;
        scanf("%d", &nn);
        unordered_map<int,int> dp;
        queue<int> que;
        dp[nn] = 0;
        que.push(nn);
        while(!que.empty()) {
            int n = que.front(); que.pop();
            //cout << "tmp == " << n << endl;
            if (n == 0) {
                cout << dp[n] << "\n";
                break;
            }
            if (dp.count(n - 1) == 0) {
                dp[n - 1] = dp[n] + 1;
                que.push(n - 1);
            }
            if (n % 2 == 0 && dp.count(n / 2) == 0) {
                dp[n / 2] = dp[n] + 1;
                que.push(n / 2);
            }
            if (n % 3 == 0 && dp.count(n / 3) == 0) {
                dp[n / 3] = dp[n] + 1;
                que.push(n / 3);
            }
        }
    }
    return 0;
}
----------------------------------------------------------------------------------------------

#include <bits/stdc++.h>

using namespace std; 

int b[10020];
int pos[10020];

int main()
{
    int n;
    scanf("%d", &n);
    vector<vector<int>> a(n);
    for (int i = 0; i < n; i++) {
        int m;
        scanf("%d", &m);
        a[i].resize(m);
        for (int j = 0; j < m; j++) {
            scanf("%d", &a[i][j]);
        }
        sort(a[i].begin(), a[i].end());
    }
    int q;
    scanf("%d", &q);
    while (q--) {
        int p, k;
        scanf("%d", &p);
        for (int i = 0; i < p; i++) {
            scanf("%d", &b[i]);
        }
        scanf("%d", &k);
        int index, Min;
        memset(pos, 0, sizeof(pos));
        while (k--) {
            index = -1;
            Min = INT_MAX;
            for (int i = 0; i < p; i++) {
                int x = b[i] - 1;
                int y = pos[b[i] - 1];
                if (y >= (int)a[x].size()) continue;
                if (a[x][y] < Min) {
                    Min = a[x][y];
                    index = i;
                }
            }
            if (index == -1) {
                break;
            }
            pos[b[index] - 1]++;
        }
        cout << Min << "\n";
        
    }
    return 0;
}
------------------------------------------------------------------------------------



#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = (int)1e5 + 10;

struct Node {
    int x, y;
}a[N];

signed main() {
    int n, w;
    scanf("%lld %lld", &n, &w);
    for (int i = 0; i < n; i++) {
        scanf("%lld %lld", &a[i].x, &a[i].y);
    }
    sort(a, a + n, [&](const Node& foo, const Node& bar){return foo.y < bar.y;});
    cout << a[n / 2].y << endl;
    return 0;
}
----------------------------------------------------------------------------------------------------

#include <bits/stdc++.h>
#define int long long
using namespace std;
int w[10010];
signed main()
{
    int tt;
    cin >> tt;
    while (tt--) {
        int n, m;
        int ans = 0;
        scanf("%lld %lld", &n, &m);
        vector<vector<int>> vec(m);
        for (int i = 0; i < n; i++) {
            scanf("%lld", &w[i]);
            vec[w[i] % m].push_back(w[i]);
            ans += w[i];
        }
        for (int i = 0; i < m; i++) {
            sort(vec[i].begin(), vec[i].end(), [&](int x, int y){return x > y;});
        }
        int sum = 0;
        for (int i = 0; i < (int)vec[0].size(); i++) sum += vec[0][i];
        if (m % 2 == 0) {
            if (vec[m / 2].size() % 2 == 0) {
                for (int i = 0; i < vec[m / 2].size(); i++) sum += vec[m / 2][i];
            } else {
                for (int i = 0; i < vec[m / 2].size(); i++) sum += vec[m / 2][i];
                sum -= vec[m / 2].back();
            }
        }
        for (int i = 1; i < (m + 1) / 2; i++) {
            int foo = i;
            int bar = m - i;
            int l = 0, r = 0;
            while (l < (int)vec[foo].size() && r < (int)vec[bar].size()) {
                sum += vec[foo][l];
                sum += vec[bar][r];
                l++;
                r++;
            }
        }
        cout << ans - sum << endl;
    }
    return 0;
}