t = int(input())
for i in range(t):
    a, b, c = map(int, input().split())
    if c % 2 == 0:
        if a > b:
            print("First")
        else:
            print("Second")
    else:
        if b > a:
            print("Second")
        else:
            print("First")

#include <bits/stdc++.h>

using namespace std;

int solve(int d, vector<int> x)
{
    int ans = 0;
    for (int i = 1; i < x.size(); i++)
    {
        ans += (x[i] - x[i - 1] - 1) / d;
    }
    ans += int(x.size()) - 2;
    return ans;
}

void solve()
{
    #define tests

    int n, m, d;
    cin >> n >> m >> d;
    vector<int> r(m);
    for (int i = 0; i < m; i++) cin >> r[i];
    r.insert(r.begin(), 1 - d);
    r.push_back(n + 1);

    int ans = 2e9;
    vector<int> res;
    for (int i = 1; i <= m; i++)
    {
        int A = r[i] - r[i - 1] - 1;
        int B = r[i + 1] - r[i] - 1;
        int C = r[i + 1] - r[i - 1] - 1;
        int D = C / d - (A / d + B / d);
        if (D < ans)
        {
            ans = D;
            res.clear();
        }
        if (D == ans)
        {
            res.push_back(r[i]);
        }
    }
    cout << ans + solve(d, r) - 1 << ' ' << res.size() << endl;
}

int main()
{
    int t = 1;
    #ifdef tests
    cin >> t;
    #endif
    while (t--)
    {
        solve();
    }
}

#include<iostream>
#include<vector>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        int cur = 0;
        for (int i = 1; i <= n; i += 2) {
            for (int j = i; j <= n; j *= 2) {
                a[cur++] = j;
            }
        }
        for (int i = 0; i<n; ++i) {
            cout << a[i] << " ";
        }
        cout << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>

#define int long long

using namespace std;
using ll = long long;

void solve();

template<typename ...Args>
void println(Args... args) {
    apply([](auto &&... args) { ((cout << args << ' '), ...); }, tuple(args...));
    cout << '\n';
}

int32_t main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    int t = 1;
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        solve();
    }
    return 0;
}

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int> max0by1(n + 1, -1e9);
    vector<vector<int>> max0pref(n + 1, vector<int>(n + 1));
    vector<vector<int>> max0suf(n + 1, vector<int>(n + 1));
    for (int l = 0; l < n; ++l) {
        int cnt1 = 0;
        for (int r = l + 1; r <= n; ++r) {
            cnt1 += s[r - 1] == '1';
            max0pref[r][cnt1] = max(max0pref[r][cnt1], r - l);
            max0suf[l][cnt1] = max(max0suf[l][cnt1], r - l);
        }
    }
    for (int r = 0; r <= n; ++r) {
        for (int cnt = 0; cnt <= n; ++cnt) {
            if (r) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r - 1][cnt]);
            if (cnt) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r][cnt - 1]);
        }
    }
    for (int l = n; l >= 0; --l) {
        for (int cnt = 0; cnt <= n; ++cnt) {
            if (l + 1 <= n) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l + 1][cnt]);
            if (cnt) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l][cnt - 1]);
        }
    }
    vector<int> ans(n + 1, -1e9);
    for (int l = 0; l < n; ++l) {
        int cnt0 = 0;
        for (int r = l; r <= n; ++r) {
            if (r > l) cnt0 += s[r - 1] == '0';
            if (cnt0 > k) break;
            max0by1[r - l] = max(max0by1[r - l], max0pref[l][k - cnt0]);
            max0by1[r - l] = max(max0by1[r - l], max0suf[r][k - cnt0]);
        }
    }
    for (int i = 0; i <= n; ++i) {
        for (int a = 1; a <= n; ++a) ans[a] = max(ans[a], i + max0by1[i] * a);
    }
    for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
    cout << '\n';
}

#include <iostream>
#include <vector>
#include <numeric>
#include <set>

using namespace std;

const int maxn = 1e6 + 1;

int f[maxn];

int get(int i) {
    int ans = 0;
    while (i >= 0) {
        ans += f[i];
        i = (i & (i + 1)) - 1;
    }
    return ans;
}

void upd(int i, int x) {
    while (i < maxn) {
        f[i] += x;
        i = i | (i + 1);
    }
}

int a[maxn];
int rev[maxn];
set<int> ids[maxn];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fill(rev, rev + maxn, -1);
    fill(a, a + maxn, -1);
    int q;
    cin >> q;
    int ptr = -1;
    vector<pair<pair<int, int>, int>> changes;
    while (q--) {
        char t;
        cin >> t;
        if (t == '?') {
            cout << get(ptr) << endl;
        } else if (t == '+') {
            int x;
            cin >> x;
            int mem = a[ptr + 1];
            if (a[ptr + 1] != -1) {
                if (ids[a[ptr + 1]].size()) {
                    upd(*ids[a[ptr + 1]].begin(), -1);
                    ids[a[ptr + 1]].erase(ptr + 1);
                }
                if (ids[a[ptr + 1]].size()) {
                    upd(*ids[a[ptr + 1]].begin(), 1);
                }
            }
            a[ptr + 1] = x;
            if (a[ptr + 1] != -1) {
                if (ids[a[ptr + 1]].size()) {
                    upd(*ids[a[ptr + 1]].begin(), -1);
                }
                ids[x].insert(ptr + 1);
                if (ids[a[ptr + 1]].size()) {
                    upd(*ids[a[ptr + 1]].begin(), 1);
                }
            }
            ++ptr;
            changes.push_back({ { 1, mem }, -1 });
        } else if (t == '-') {
            int k;
            cin >> k;
            ptr -= k;
            changes.push_back({ { -1, k }, -1 });
        } else {
            if (changes.back().first.first == 1) {
                if (a[ptr] != -1) {
                    if (ids[a[ptr]].size()) {
                        upd(*ids[a[ptr]].begin(), -1);
                        ids[a[ptr]].erase(ptr);
                    }
                    if (ids[a[ptr]].size()) {
                        upd(*ids[a[ptr]].begin(), 1);
                    }
                }
                a[ptr] = changes.back().first.second;
                --ptr;
                if (a[ptr + 1] != -1) {
                    if (ids[a[ptr + 1]].size()) {
                        upd(*ids[a[ptr + 1]].begin(), -1);
                    }
                    ids[a[ptr + 1]].insert(ptr + 1);
                    if (ids[a[ptr + 1]].size()) {
                        upd(*ids[a[ptr + 1]].begin(), 1);
                    }
                }
            } else {
                ptr += changes.back().first.second;
            }
            changes.pop_back();
        }
    }
}

Количество различных элементов на отрезке

Дан массив A длины n и q запросов.

Запросы:

• Найти количество различных элементов на отрезке [l; r] массива A.

Количество различных элементов на отрезке с изменением

Дан массив A длины n и q запросов.

Необходимо уметь:

• Находить количество различных элементов на отрезке

• Изменять элемент

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> a, cnt;

int ans = 0;

inline void add(int i) {
    ++cnt[a[i]];
    if (cnt[a[i]] == 1) { //  cnt[a[i]] == 1 <=> we have not met it before.
        ++ans;
    }
}

inline void del(int i) {
    --cnt[a[i]];
    if (cnt[a[i]] == 0) { //  cnt[a[i]] == 0 <=> there are no integers = a[i] left.
        --ans;
    }
}

struct query {
    int l, r, i;

    query() {}

    query(int l, int r, int i): l(l), r(r), i(i) {}
};

inline bool cmp(query &a, query &b) {
    if (a.l / k == b.l / k) {
        return a.r < b.r;
    }
    return a.l < b.l; //  <=> a.l / k < b.l / k
}

int main() {
    int n, q;
    cin >> n >> q;
    a.resize(n);
    cnt.assign(1000000, 0);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<query> qq;
    int i = 0;
    while (q--) {
        int l, r;
        cin >> l >> r;
        qq.push_back(query(l - 1, r - 1, i++));
    }
    sort(qq.begin(), qq.end(), cmp);
    int L = 0, R = -1;
    vector<int> answer(qq.size(), 0);
    for (query x : qq) {
        int l = x.l, r = x.r, i = x.i;
        while (R < r) {
            add(++R);
        }
        while (L > l) {
            add(--L);
        }
        while (R > r) {
            del(R--);
        }
        while (L < l) {
            del(L++);
        }
        answer[i] = ans;
    }
    for(int i : answer) {
        cout << i << '\n';
    }
}

Мы можем не уметь удалять элементы.

• В первом алгоритме иногда необходимо писать 4 функции добавления/удаления (add_left, add_right, del_left, del_right).

• При использовании второго алгоритма достаточно add_left, add_right, так как вместо удалений можно делать откаты.

Воспользуемся первым алгоритмом Мо.

L = 0, R = -1
for block_of_queries in blocks:
    for ask_query in block:
        while(L > ask_query.l) add(--L)
        while(R < ask_query.r) add(++R)
        while(L < ask_query.l) del(L++)
        while(R > ask_query.r) del(R--)
        changes = []
        for change_query in block:
            if (has_influence(ask_query, change_query)):
                del(change_query.i) 
                changes.append([array[change_query.i], change_query.i])
                array[change_query.i] = change_query.val
                add(chenge_query.i)
        ans[ask_query].i = global_answer
        reverse(changes)
        for change in changes:
            del(change.i)
            array[changes.i] = change.val
            add(change.i)

for left_bucket:
    for right_bucket:
        last_unused = 0
        L = 0, R = -1
        array = input_array
        for query with l in left_bucket && r in right_bucket:
            move L
            move R
            while last_unused <= query.i:
                if (L <= change[last_unused].idx <= R):
                    delete(change[last_unused].idx)
                    array[change[last_unused].idx] = change[last_unused].val
                    add(change[last_unused.idx])
                else:
                    array[change[last_unused].idx] = change[last_unused].val
                ++last_unused
             ans[query.i] = answer

Дан массив.

Необходимо:

• Изменять элемент в точке.

• Найти mex на отрезке (наименьшее целое неотрицательное число, которое не встречается на этом отрезке).

$$$O(n^{\frac{5}{3}})$$$

Дан массив.

Необходимо:

• Изменять элемент в точке.

• Найти mex {$$$c_{1}, c_{2}, ..., c_{10^{5}}$$$}, где $$$c_{i}$$$ — количество элементов, которые равны i (mex — наименьшее целое неотрицательное число, которое не в данном множестве).

$$$O(n^{\frac{5}{3}})$$$

Дан массив.

Необходимо:

• Изменять элемент в точке.

• Найти количество делителей числа x = $$$a_{l}$$$ $$$\cdot$$$ $$$a_{l + 1}$$$ $$$\cdot$$$ ... $$$\cdot$$$ $$$a_{r}$$$ по модулю $$$10^{9} + 7$$$.

$$$O(n^{\frac{5}{3}} + q \ log_{2} \ mod)$$$

Дано дерево, в каждой вершине которого написано 4 числа — левый нижний и правый верхний угол прямоугольника.

Необходимо:

• Находить пересечение прямоугольников в вершинах на пути из u в v.

$$$O(n \sqrt n)$$$

Дано дерево с числами на ребрах.

Необходимо:

• Находить mex чисел, написанных на ребрах пути из u в v в дереве.

$$$O(n \sqrt n)$$$

Дано дерево с числами на ребрах

Необходимо:

• Изменять число в вершине.

• Находить mex чисел, написанных на ребрах пути из u в v в дереве.

$$$O(n^{\frac{5}{3}})$$$

Дано дерево с числами в вершинах.

Необходимо:

• Изменять число в вершине.

• Находить количество делителей числа, которое равно произведению чисел в вершинах на пути из u в v (по модулю $$$10^{9} + 7$$$).

$$$O(n^{\frac{5}{3}} + q \ log_{2} \ mod)$$$