using namespace std;
using vi = vector<int>;
struct fenwick
{
    int n;
    vi bit;
    fenwick() {}
    fenwick(int n_) : n(n_ + 1) { bit.assign(n_ + 1, 0); }
    void update(int i, int delta)
    {
        while (i < n)
        {
            bit[i] += delta;
            i += (i & -i);
        }
    }
    int prefix_sum(int r) const
    {
        int ans = 0;
        while (r > 0)
        {
            ans += bit[r];
            r -= (r & -r);
        }
        return ans;
    }
    int sum(int l, int r) const { return prefix_sum(r) - prefix_sum(l - 1); }
};
fenwick zcnt, ncnt;
vi a;
void change(int i, int v)
{
    if ((a[i] == 0 and v == 0) or (a[i] < 0 and v < 0))
        return;
    if (a[i] == 0)
    {
        zcnt.update(i, -1);
        if (v < 0)
            ncnt.update(i, +1);
    }
    else if (a[i] < 0)
    {
        ncnt.update(i, -1);
        if (v == 0)
            zcnt.update(i, +1);
    }
    else
    {
        if (v == 0)
            zcnt.update(i, +1);
        else if (v < 0)
            ncnt.update(i, +1);
    }
}
char product(int l, int r)
{
    int zeros = zcnt.sum(l, r);
    if (zeros > 0)
        return '0';
    int neg = ncnt.sum(l, r);
    if (neg % 2 == 0)
        return '+';
    else
        return '-';
}
int main(void)
{
    int n, k, l, r, j, x;
    char type;
    while (cin >> n >> k)
    {
        a = vi(n + 1);
        zcnt = fenwick(n);
        ncnt = fenwick(n);
        for (int i = 1; i <= n; ++i)
        {
            cin >> a[i];
            if (a[i] == 0)
                zcnt.update(i, 1);
            else if (a[i] < 0)
                ncnt.update(i, 1);
        }
        while (k--)
        {
            cin >> type;
            if (type == 'C')
            {
                cin >> j >> x;
                change(j, x);
                a[j] = x;
            }
            else
            {
                cin >> l >> r;
                cout << product(l, r);
            }
        }
        cout << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using vi = vector<int>;
int const NMAX = 1e5;
ll const INF = 1e17;
int n, c[3][NMAX];
vi g[NMAX];
int main(void)
{
    int u, v;
    cin >> n;
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < n; ++j)
            cin >> c[i][j];
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v, u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    try
    {
        int leaf = distance(
            g, find_if(g, g + n, [](vi const &adj) { return (int)adj.size() == 1; }));
        vi a(n), p = {0, 1, 2};
        int prv = -1, u = leaf;
        for (int i = 0; i < n; ++i)
        {
            a[i] = u;
            if (prv != -1)
                g[u].erase(find(g[u].begin(), g[u].end(), prv));
            if ((int)g[u].size() > 1)
                throw -1;
            if (i < n - 1)
            {
                prv = u;
                u = g[u].back();
            }
        }
        vector<vi> ps(6);
        int k;
        ll ans = INF;
        for (int i = 0; i < 6; ++i, next_permutation(p.begin(), p.end()))
        {
            ps[i] = p;
            ll cur = 0;
            for (int j = 0; j < n; ++j)
                cur += c[p[j % 3]][a[j]];
            if (cur < ans)
            {
                ans = cur;
                k = i;
            }
        }
        vi ansv(n);
        for (int i = 0; i < n; ++i)
            ansv[a[i]] = ps[k][i % 3] + 1;
        cout << ans << endl;
        for (int i = 0; i < n; ++i)
            cout << ansv[i] << " ";
        cout << endl;
    }
    catch (int e)
    {
        cout << e << endl;
    }
    return 0;
}

using namespace std;
int main(void)
{
    int t, n, x, s;
    cin >> t;
    while (t--)
    {
        s = 0;
        cin >> n;
        for (int i = 0; i < n; ++i)
        {
            cin >> x;
            s += x;
        }
        cout << (int)ceil(s / (n * 1.0)) << endl;
    }
}

using namespace std;
int time_spent(int x, int d) { return x + (int)ceil((d * 1.0) / (x + 1)); }
int binary_search(int n, int d) {
  int l = 1;
  int h = d - 1;
  while (l <= h) {
    int mid1 = l + (h - l) / 3;
    int mid2 = h - (h - l) / 3;
    int ans1 = time_spent(mid1, d);
    int ans2 = time_spent(mid2, d);
    if (ans1 <= n or ans2 <= n)
      return 1;
    else {
      if (ans1 < ans2)
        h = mid2 - 1;
      else {
        l = mid1 + 1;
      }
    }
  }
  return -1;
}
bool solve(int n, int d) {
  if (d <= n or binary_search(n, d) != -1)
    return true;
  return false;
}
int main(void) {
  int T;
  cin >> T;
  while (T--) {
    int n, d;
    cin >> n >> d;
    if (solve(n, d))
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
  return 0;
}

using namespace std;
using vi = vector<int>;
int const INF = 1e9;
int const NMAX = 2e5 + 11;
int k, best_cost[NMAX];
deque<int> costs[NMAX];
void build() { fill(best_cost, best_cost + NMAX, INF); }
int query(int x) { return (int)costs[x].size() == k ? best_cost[x] : INF; }
void insert(int x, int cur_cost)
{
    if ((int)costs[x].size() == 0)
        best_cost[x] = 0;
    costs[x].push_back(cur_cost);
    if ((int)costs[x].size() > k)
    {
        best_cost[x] -= costs[x].front();
        costs[x].pop_front();
    }
    best_cost[x] += cur_cost;
}
int solve(vi a)
{
    int ans = INF;
    vi cnt(NMAX, 0);
    vector<vi> best_cost(NMAX, vi(log2(NMAX) + 5, 0));
    sort(a.begin(), a.end());
    for_each(a.rbegin(), a.rend(), [&ans](int ai) {
        for (int i = 0, m = log2(ai) + 2; i < m; ++i, ai /= 2)
        {
            insert(ai, i);
            ans = min(ans, query(ai));
        }
    });
    return ans;
}
int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n;
    vi a;
    cin >> n >> k;
    a.resize(n);
    for (auto &ai : a)
        cin >> ai;
    build();
    cout << solve(a) << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
const int NMAX = 2e5 + 11;
struct fenwick
{
    int n;
    vi bit;
    fenwick() {}
    fenwick(int n_) : n(n_ + 1) { bit.assign(n_ + 1, 0); };
    void update(int i, int delta)
    {
        while (i < n)
        {
            bit[i] += delta;
            i += i & -i;
        }
    }
    int psum(int r)
    {
        int ans = 0;
        while (r > 0)
        {
            ans += bit[r];
            r -= r & -r;
        }
        return ans;
    }
    int sum(int l, int r) { return psum(r) - psum(l - 1); }
};
int n, potmeter[NMAX];
fenwick t;
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int x, y, r, test = 1;
    char type;
    while (cin >> n)
    {
        if (n == 0)
            break;
        else if (test != 1)
            cout << endl;
        t = fenwick(n);
        for (int i = 1; i <= n; ++i)
        {
            cin >> x;
            potmeter[i] = x;
            t.update(i, x);
        }
        cout << "Case " << test << ":" << endl;
        while (cin >> type and type != 'E')
        {
            if (type == 'S')
            {
                cin >> x >> r;
                t.update(x, r - potmeter[x]);
                potmeter[x] = r;
            }
            else if (type == 'M')
            {
                cin >> x >> y;
                cout << t.sum(x, y) << endl;
            }
        }
        cin.ignore(), cin.ignore();
        test += 1;
    }
    return 0;
}

using namespace std;
using ll = long long;
const int NMAX = 4e5 + 11;
ll n, a[NMAX];
ll gcd(ll a, ll b) { return (b == 0 ? a : gcd(b, a % b)); }
ll solve(void)
{
    ll ngcd = a[0], ans = 0;
    for (int i = 1; i < n; ++i)
        ngcd = gcd(ngcd, a[i]);
    for (ll i = 1; i <= sqrt(ngcd); ++i)
    {
        if (ngcd % i == 0)
        {
            if (ngcd / i == i)
                ++ans;
            else
                ans += 2;
        }
    }
    return ans;
}
int main(void)
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    cout << solve() << endl;
    return 0;
}

using namespace std;
using ll = long long;
using predicate = function<bool(int)>;
int bs(int l, int r, predicate p)
{
    while (l < r)
    {
        int m = l + (r - l) / 2;
        if (p(m))
            r = m;
        else
            l = m + 1;
    }
    return l;
}
ll psum(ll n) { return (n * (n + 1)) / 2; }
int main(void)
{
    int x;
    cin >> x;
    x = abs(x);
    int n = bs(0, 1e9 + 11, [x](ll n) { return x <= psum(n); });
    while (psum(n) % 2 != x % 2)
        ++n;
    cout << n << endl;
    return 0;
}

using namespace std;
using ll = long long;
using iii = array<int, 3>;
int n, m;
vector<iii> edges;
vector<int> visited;
const ll INF = 1e17;
vector<int> bellman_ford(int src)
{
    int x = -1;
    vector<ll> d(n + 1, INF);
    vector<ll> p(n + 1);
    d[src] = 0;
    for (int i = 1; i <= n; ++i)
    {
        bool change = false;
        for (auto [u, v, c] : edges)
        {
            if (d[u] < INF and d[u] + c < d[v])
            {
                visited[u] = visited[v] = true;
                change = true;
                d[v] = max(-INF, d[u] + c);
                p[v] = u;
                if (i == n)
                    x = v;
            }
        }
        if (not change)
            break;
    }
    if (x == -1)
    {
        return {};
    }
    else
    {
        int y = x;
        for (int i = 0; i < n; ++i)
            y = p[y];
        vector<int> ans;
        int cur = y;
        do
        {
            ans.push_back(cur);
            cur = p[cur];
        } while (cur != y);
        ans.push_back(cur);
        reverse(ans.begin(), ans.end());
        return ans;
    }
}
vector<int> get_neg_cycle(void)
{
    for (int u = 1; u <= n; ++u)
    {
        if (not visited[u])
        {
            if (auto ans = bellman_ford(u); not ans.empty())
            {
                return ans;
            }
        }
    }
    return {};
}
int main(void)
{
    cin >> n >> m;
    edges.resize(m);
    visited.assign(n + 1, false);
    for (auto &[u, v, c] : edges)
        cin >> u >> v >> c;
    if (auto ans = get_neg_cycle(); not ans.empty())
    {
        cout << "YES" << endl;
        for (auto x : ans)
            cout << x << " ";
        cout << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vii = vector<pair<int, int>>;
using viii = vector<array<int, 3>>;
const ll INF = 1e16;
vll dijkstra(vii g[], int n, int src)
{
    vector<long long> distance(n + 1, INF);
    vector<bool> processed(n + 1, false);
    priority_queue<pair<ll, int>> q;
    distance[src] = 0;
    q.push({0, src});
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (processed[u])
            continue;
        processed[u] = true;
        for (auto [v, c] : g[u])
        {
            if (distance[u] + c < distance[v])
            {
                distance[v] = distance[u] + c;
                q.push({-distance[v], v});
            }
        }
    }
    return distance;
}
int main(void)
{
    int n, m, u, v, c;
    cin >> n >> m;
    vii g[n + 1], gi[n + 1];
    viii edges(m);
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v >> c;
        g[u].emplace_back(v, c);
        gi[v].emplace_back(u, c);
        edges[i] = {u, v, c};
    }
    auto from_src = dijkstra(g, n, 1);
    auto to_dst = dijkstra(gi, n, n);
    ll ans = INF;
    for (auto [u, v, c] : edges)
        ans = min(ans, from_src[u] + c / 2 + to_dst[v]);
    cout << ans << endl;
    return 0;
}