結果
| 問題 |
No.3301 Make Right Triangle
|
| ユーザー |
 7deQSJCy8c4Hg7I
|
| 提出日時 | 2025-10-05 16:04:03 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 35,127 bytes |
| コンパイル時間 | 3,320 ms |
| コンパイル使用メモリ | 300,324 KB |
| 実行使用メモリ | 150,684 KB |
| 最終ジャッジ日時 | 2025-10-05 16:04:36 |
| 合計ジャッジ時間 | 9,955 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | TLE * 1 -- * 8 |
コンパイルメッセージ
main.cpp: In static member function ‘static int ArbitraryModInt::set_mod(int)’:
main.cpp:614:46: warning: no return statement in function returning non-void [-Wreturn-type]
614 | static int set_mod(int md) { mod() = md; }
| ^
ソースコード
#include <bits/stdc++.h>
using namespace std;
#include <cassert>
#include <functional>
using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;
using vi = vector<int>;
using vl = vector<long long>;
using vll = vector<ll>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvvvll = vector<vvvll>;
using vvvvvll = vector<vvvvll>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vld = vector<long double>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vc = vector<char>;
using vvc = vector<vc>;
using lll = __int128_t;
using vs = vector<string>;
using pii = pair<long long, long long>;
#define mp make_pair
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) n.begin(), n.end()
#define rALL(n) n.rbegin(), n.rend()
#define fore(i, a) for (auto &i : a)
#define IN(a, x, b) (a <= x && x < b)
#define IN(a, x, b) (a <= x && x < b)
#define INIT \
std::ios::sync_with_stdio(false); \
std::cin.tie(0);
template <typename T>
// [0,M)についての階上を求める
vector<T> KAI(int M) {
vector<T> kai(M, 1);
rep(i, M - 1) { kai[i + 1] = kai[i] * (i + 1); }
return kai;
}
template <typename T>
vector<T> DIV(int M) {
vector<T> kai = KAI<T>(M), div(M, 1);
rep(i, M - 1) { div[i + 1] = 1 / kai[i + 1]; }
return div;
}
long long Power(long long a, long long b, long long m) {
long long p = a, Answer = 1;
p %= m;
for (int i = 0; i < 63; i++) {
ll wari = (1LL << i);
if ((b / wari) % 2 == 1) {
Answer %= m;
Answer = (Answer * p) % m;
// 「a の 2^i 乗」が掛けられるとき
}
ll t = p % m;
p = (t * t) % m;
// cout << p << endl;
}
return Answer;
}
// a ÷ b を m で割った余りを返す関数
long long Division(long long a, long long b, long long m) {
return (a * Power(b, m - 2, m)) % m;
}
template <class T>
void output(T &W, bool x) {
cout << W;
if (!x)
cout << ' ';
else
cout << '\n';
return;
}
// sは改行するか否かを表す
template <class T>
void output(vector<T> &W, bool s) {
rep(i, W.size()) { output(W[i], ((i == W.size() - 1) || s)); }
return;
}
// sは改行するか否かを表す
template <class T>
void output(vector<vector<T>> &W, bool s) {
rep(i, W.size()) { output(W[i], s); }
return;
}
template <class T>
T vectorsum(vector<T> &W, int a, int b) {
return accumulate(W.begin() + a, W.end() + b, (T)0);
}
template <class T>
T vectorsum(vector<T> &W) {
int b = W.size();
return accumulate(ALL(W), (T)0);
}
template <class T>
inline T CHMAX(T &a, const T b) {
return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T &a, const T b) {
return a = (a > b) ? b : a;
}
template <class T>
void input(T &W) {
cin >> W;
return;
}
template <class T>
void input(vector<T> &W) {
for (auto &u : W) input(u);
return;
}
template <class T, class TT>
void add(T &W, TT &a) {
W += a;
return;
}
template <class T>
void add(vector<T> &W, vector<T> &a) {
rep(i, W.size()) add(W[i], a[i]);
}
template <class T>
void add(T &W, T &a) {
W += a;
}
template <class T, class TT>
void add(vector<T> &W, TT a) {
for (auto &u : W) add(u, a);
return;
}
const double PI = acos(-1.0L);
const long double EPS = 1e-10;
const double INF = 1e18;
struct TRI {
ll a;
ll b;
ll c;
ll d;
};
bool operator>(const TRI &r, const TRI &l) {
return (r.a > l.a | (r.a == l.a & r.b > l.b) |
(r.a == l.a & r.b == l.b & r.c > l.c));
}
bool operator<(const TRI &r, const TRI &l) {
return (r.a < l.a | (r.a == l.a & r.b < l.b) |
(r.a == l.a & r.b == l.b & r.c < l.c));
}
struct TRK {
ll a;
ll b;
ll c;
};
bool operator>(const TRK &r, const TRK &l) {
return (r.a > l.a | (r.a == l.a & r.b > l.b) |
(r.a == l.a & r.b == l.b & r.c > l.c));
}
bool operator<(const TRK &r, const TRK &l) {
return (r.a < l.a | (r.a == l.a & r.b < l.b) |
(r.a == l.a & r.b == l.b & r.c < l.c));
}
#include <bits/stdc++.h>
using namespace std;
// 実装はUnion by sizeで行っている
class UnionFind {
public:
UnionFind() = default;
/// @param n 要素数
explicit UnionFind(size_t n) : m_parentsOrSize(n, -1), N(n) {}
/// @brief 頂点 i の root のインデックスを返します。
/// @param i 調べる頂点のインデックス
/// @return 頂点 i の root のインデックス
int leader(int i) {
if (m_parentsOrSize[i] < 0) {
return i;
}
const int root = leader(m_parentsOrSize[i]);
// 経路圧縮
return (m_parentsOrSize[i] = root);
}
/// @param w (b の重み) - (a の重み)
/// a を含むグループと b を含むグループを併合する
// グループが一致している場合何もしない
void merge(int a, int b) {
a = leader(a);
b = leader(b);
if (a != b) {
// union by size (小さいほうが子になる）
if (-m_parentsOrSize[a] < -m_parentsOrSize[b]) {
std::swap(a, b);
}
m_parentsOrSize[a] += m_parentsOrSize[b];
m_parentsOrSize[b] = a;
}
}
/// @brief a と b が同じグループに属すかを返します。
/// @param a 一方のインデックス
/// @param b 他方のインデックス
/// @return a と b が同じグループに属す場合 true, それ以外の場合は false
/// a と b が同じグループに属すかを返す
bool same(int a, int b) { return (leader(a) == leader(b)); }
/// @brief i が属するグループの要素数を返します。
/// @param i インデックス
/// @return i が属するグループの要素数
int size(int i) { return -m_parentsOrSize[leader(i)]; }
vector<vector<int>> Groups() {
vector<vector<int>> G;
int sum = 0;
vector<int> number(N, -1);
for (int i = 0; i < N; i++) {
int a = leader(i);
if (number[a] == -1) {
number[a] = sum;
G.emplace_back(vector<int>{});
G[sum].emplace_back(i);
sum++;
} else {
G[number[i]].emplace_back(i);
}
}
return G;
}
private:
// m_parentsOrSize[i] は i の 親,
// ただし root の場合は (-1 * そのグループに属する要素数)
int N;
std::vector<int> m_parentsOrSize;
};
struct Mo {
int n;
vector<pair<int, int>> lr;
explicit Mo(int n) : n(n) {}
void add(int l, int r) { /* [l, r) */ lr.emplace_back(l, r); }
template <typename AL, typename AR, typename EL, typename ER, typename O>
void build(const AL &add_left, const AR &add_right, const EL &erase_left,
const ER &erase_right, const O &out) {
int q = (int)lr.size();
int bs = n / min<int>(n, sqrt(q));
vector<int> ord(q);
iota(begin(ord), end(ord), 0);
sort(begin(ord), end(ord), [&](int a, int b) {
int ablock = lr[a].first / bs, bblock = lr[b].first / bs;
if (ablock != bblock) return ablock < bblock;
return (ablock & 1) ? lr[a].second > lr[b].second
: lr[a].second < lr[b].second;
});
int l = 0, r = 0;
for (auto idx : ord) {
while (l > lr[idx].first) add_left(--l);
while (r < lr[idx].second) add_right(r++);
while (l < lr[idx].first) erase_left(l++);
while (r > lr[idx].second) erase_right(--r);
out(idx);
}
}
template <typename A, typename E, typename O>
void build(const A &add, const E &erase, const O &out) {
build(add, add, erase, erase, out);
}
};
vector<bool> Eratosthenes(int N) {
vector<bool> R(N + 1, true);
R[0] = R[1] = false;
for (int p = 2; p <= N; ++p) {
if (!R[p]) continue;
for (int q = p * 2; q <= N; q += p) {
R[q] = false;
}
}
return R;
}
#include <bits/stdc++.h>
using namespace std;
// 抽象化セグメント木
template <typename T>
struct segment_tree {
private:
int n{}, sz{}, height{};
vector<T> node;
T (*combine)(T, T); // 区間の結合を行う演算
T (*identity)(); // 単位元
void update(int k) { node[k] = combine(node[2 * k], node[2 * k + 1]); }
public:
segment_tree() {}
segment_tree(int n, T (*combine)(T, T), T (*identity)())
: n(n), combine(combine), identity(identity) {
sz = 1;
height = 0;
while (sz < n) sz <<= 1, height++;
node = vector<T>(2 * sz, identity());
}
segment_tree(vector<T> &A, T (*combine)(T, T), T (*identity)())
: n((int)A.size()), combine(combine), identity(identity) {
sz = 1;
height = 0;
while (sz < n) sz <<= 1, height++;
node = vector<T>(2 * sz, identity());
for (int i = 0; i < (int)A.size(); i++) {
node[sz + i] = A[i];
}
for (int i = sz - 1; i > 0; --i) {
node[i] = combine(node[2 * i], node[2 * i + 1]);
}
}
T get(int k) { return node[k + sz]; }
T operator[](int i) {
assert(0 <= i && i < n);
return node[i + sz];
}
void set(int i, T x) {
assert(0 <= i && i < n);
i += sz;
node[i] = x;
for (int k = 1; k <= height; k++) update(i >> k);
}
T prod(int l, int r) {
assert(0 <= l && l <= r && r <= n);
T res = identity(); // 初期値は単位元
T res2 = identity();
for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
// 区間内のものを左右から結合
if (l & 1) res = combine(res, node[l++]);
if (r & 1) res2 = combine(node[--r], res2);
}
return combine(res, res2);
}
T all_prod() { return prod(0, n); }
template <typename C>
int max_right(int l, const C &check) {
if (l >= n) return n;
l += sz;
T sum = identity();
do {
while ((l & 1) == 0) l >>= 1;
if (!check(combine(sum, node[l]))) {
while (l < sz) {
l <<= 1;
auto nxt = combine(sum, node[l]);
if (check(nxt)) {
sum = nxt;
l++;
}
}
return l - sz;
}
sum = combine(sum, node[l++]);
} while ((l & -l) != l);
return n;
}
template <typename C>
int min_left(int r, const C &check) {
if (r <= 0) return 0;
r += sz;
T sum = identity();
do {
r--;
while (r > 1 and (r & 1)) r >>= 1;
if (!check(combine(node[r], sum))) {
while (r < sz) {
r = (r << 1) + 1;
auto nxt = combine(node[r], sum);
if (check(nxt)) {
sum = nxt;
r--;
}
}
return r - sz;
}
sum = combine(node[r], sum);
} while ((r & -r) != r);
return 0;
}
};
void Yes(bool b) {
if (b)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
}
// 参考(https://pione.hatenablog.com/entry/2021/02/27/061552)
class Dinic {
private:
const int INF = 1e9;
vector<int> level, itr;
struct Edge {
int to, rev;
int cap;
Edge(int to, int rev, int cap) : to(to), rev(rev), cap(cap) {};
};
vector<vector<Edge>> G;
Edge &get_rev(Edge &edge) { return G[edge.to][edge.rev]; }
void bfs(int s) {
level.assign(G.size(), -1);
level[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto v = q.front();
q.pop();
for (auto &e : G[v]) {
if (level[e.to] < 0 and e.cap > 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
int dfs(int v, int t, int flow) {
if (v == t) return flow;
for (int &i = itr[v]; i < G[v].size(); i++) {
auto &edge = G[v][i];
if (level[v] < level[edge.to] and edge.cap > 0) {
auto f = dfs(edge.to, t, min(flow, edge.cap));
if (f > 0) {
edge.cap -= f;
get_rev(edge).cap += f;
return f;
}
}
}
return 0;
}
public:
Dinic(int n) { G.resize(n); }
void add_edge(int from, int to, int cap) {
G[from].push_back(Edge(to, (int)G[to].size(), cap));
G[to].push_back(Edge(from, (int)G[from].size() - 1, 0));
}
int get_max_flow(int s, int t) {
int n = G.size();
int res = 0;
while (true) {
itr.assign(n, 0);
bfs(s);
if (level[t] < 0) break;
while (true) {
int flow = dfs(s, t, INF);
if (flow > 0)
res += flow;
else
break;
}
}
return res;
}
};
/*https://ei1333.github.io/luzhiled/snippets/math/fast-fourier-transform.html*/
namespace FastFourierTransform {
using real = double;
struct C {
real x, y;
C() : x(0), y(0) {}
C(real x, real y) : x(x), y(y) {}
inline C operator+(const C &c) const { return C(x + c.x, y + c.y); }
inline C operator-(const C &c) const { return C(x - c.x, y - c.y); }
inline C operator*(const C &c) const {
return C(x * c.x - y * c.y, x * c.y + y * c.x);
}
inline C conj() const { return C(x, -y); }
};
const real PI = acosl(-1);
int base = 1;
vector<C> rts = {{0, 0}, {1, 0}};
vector<int> rev = {0, 1};
void ensure_base(int nbase) {
if (nbase <= base) return;
rev.resize(1 << nbase);
rts.resize(1 << nbase);
for (int i = 0; i < (1 << nbase); i++) {
rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
}
while (base < nbase) {
real angle = PI * 2.0 / (1 << (base + 1));
for (int i = 1 << (base - 1); i < (1 << base); i++) {
rts[i << 1] = rts[i];
real angle_i = angle * (2 * i + 1 - (1 << base));
rts[(i << 1) + 1] = C(cos(angle_i), sin(angle_i));
}
++base;
}
}
void fft(vector<C> &a, int n) {
assert((n & (n - 1)) == 0);
int zeros = __builtin_ctz(n);
ensure_base(zeros);
int shift = base - zeros;
for (int i = 0; i < n; i++) {
if (i < (rev[i] >> shift)) {
swap(a[i], a[rev[i] >> shift]);
}
}
for (int k = 1; k < n; k <<= 1) {
for (int i = 0; i < n; i += 2 * k) {
for (int j = 0; j < k; j++) {
C z = a[i + j + k] * rts[j + k];
a[i + j + k] = a[i + j] - z;
a[i + j] = a[i + j] + z;
}
}
}
}
vector<int64_t> multiply(const vector<int> &a, const vector<int> &b) {
int need = (int)a.size() + (int)b.size() - 1;
int nbase = 1;
while ((1 << nbase) < need) nbase++;
ensure_base(nbase);
int sz = 1 << nbase;
vector<C> fa(sz);
for (int i = 0; i < sz; i++) {
int x = (i < (int)a.size() ? a[i] : 0);
int y = (i < (int)b.size() ? b[i] : 0);
fa[i] = C(x, y);
}
fft(fa, sz);
C r(0, -0.25 / (sz >> 1)), s(0, 1), t(0.5, 0);
for (int i = 0; i <= (sz >> 1); i++) {
int j = (sz - i) & (sz - 1);
C z = (fa[j] * fa[j] - (fa[i] * fa[i]).conj()) * r;
fa[j] = (fa[i] * fa[i] - (fa[j] * fa[j]).conj()) * r;
fa[i] = z;
}
for (int i = 0; i < (sz >> 1); i++) {
C A0 = (fa[i] + fa[i + (sz >> 1)]) * t;
C A1 = (fa[i] - fa[i + (sz >> 1)]) * t * rts[(sz >> 1) + i];
fa[i] = A0 + A1 * s;
}
fft(fa, sz >> 1);
vector<int64_t> ret(need);
for (int i = 0; i < need; i++) {
ret[i] = llround(i & 1 ? fa[i >> 1].y : fa[i >> 1].x);
}
return ret;
}
}; // namespace FastFourierTransform
/*https://ei1333.github.io/luzhiled/snippets/math/mod-int.html*/
struct ArbitraryModInt {
int x;
ArbitraryModInt() : x(0) {}
ArbitraryModInt(int64_t y)
: x(y >= 0 ? y % mod() : (mod() - (-y) % mod()) % mod()) {}
static int &mod() {
static int mod = 0;
return mod;
}
static int set_mod(int md) { mod() = md; }
ArbitraryModInt &operator+=(const ArbitraryModInt &p) {
if ((x += p.x) >= mod()) x -= mod();
return *this;
}
ArbitraryModInt &operator-=(const ArbitraryModInt &p) {
if ((x += mod() - p.x) >= mod()) x -= mod();
return *this;
}
ArbitraryModInt &operator*=(const ArbitraryModInt &p) {
unsigned long long a = (unsigned long long)x * p.x;
unsigned xh = (unsigned)(a >> 32), xl = (unsigned)a, d, m;
asm("divl %4; \n\t" : "=a"(d), "=d"(m) : "d"(xh), "a"(xl), "r"(mod()));
x = m;
return *this;
}
ArbitraryModInt &operator/=(const ArbitraryModInt &p) {
*this *= p.inverse();
return *this;
}
ArbitraryModInt operator-() const { return ArbitraryModInt(-x); }
ArbitraryModInt operator+(const ArbitraryModInt &p) const {
return ArbitraryModInt(*this) += p;
}
ArbitraryModInt operator-(const ArbitraryModInt &p) const {
return ArbitraryModInt(*this) -= p;
}
ArbitraryModInt operator*(const ArbitraryModInt &p) const {
return ArbitraryModInt(*this) *= p;
}
ArbitraryModInt operator/(const ArbitraryModInt &p) const {
return ArbitraryModInt(*this) /= p;
}
bool operator==(const ArbitraryModInt &p) const { return x == p.x; }
bool operator!=(const ArbitraryModInt &p) const { return x != p.x; }
ArbitraryModInt inverse() const {
int a = x, b = mod(), u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return ArbitraryModInt(u);
}
ArbitraryModInt pow(int64_t n) const {
ArbitraryModInt ret(1), mul(x);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const ArbitraryModInt &p) {
return os << p.x;
}
friend istream &operator>>(istream &is, ArbitraryModInt &a) {
int64_t t;
is >> t;
a = ArbitraryModInt(t);
return (is);
}
};
/*https://ei1333.github.io/luzhiled/snippets/math/mod-int.html*/
template <int mod = 1000000007>
struct ModInt {
int x;
ModInt() : x(0) {}
ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
ModInt &operator+=(const ModInt &p) {
if ((x += p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator-=(const ModInt &p) {
if ((x += mod - p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator*=(const ModInt &p) {
x = (int)(1LL * x * p.x % mod);
return *this;
}
ModInt &operator/=(const ModInt &p) {
*this *= p.inverse();
return *this;
}
ModInt operator-() const { return ModInt(-x); }
ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
bool operator==(const ModInt &p) const { return x == p.x; }
bool operator!=(const ModInt &p) const { return x != p.x; }
ModInt inverse() const {
int a = x, b = mod, u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return ModInt(u);
}
ModInt pow(int64_t n) const {
ModInt ret(1), mul(x);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const ModInt &p) {
return os << p.x;
}
friend istream &operator>>(istream &is, ModInt &a) {
int64_t t;
is >> t;
a = ModInt<mod>(t);
return (is);
}
static int get_mod() { return mod; }
};
using modint = ModInt<1000000007>;
/*
https://ei1333.github.io/luzhiled/snippets/math/arbitrary-mod-convolution.html
*/
// Sはdataを表している。
template <typename T>
struct ArbitraryModConvolution {
using real = FastFourierTransform::real;
using C = FastFourierTransform::C;
ArbitraryModConvolution() = default;
vector<T> multiply(const vector<T> &a, const vector<T> &b, int need = -1) {
if (need == -1) need = a.size() + b.size() - 1;
int nbase = 0;
while ((1 << nbase) < need) nbase++;
FastFourierTransform::ensure_base(nbase);
int sz = 1 << nbase;
vector<C> fa(sz);
for (int i = 0; i < a.size(); i++) {
fa[i] = C(a[i].x & ((1 << 15) - 1), a[i].x >> 15);
}
fft(fa, sz);
vector<C> fb(sz);
if (a == b) {
fb = fa;
} else {
for (int i = 0; i < b.size(); i++) {
fb[i] = C(b[i].x & ((1 << 15) - 1), b[i].x >> 15);
}
fft(fb, sz);
}
real ratio = 0.25 / sz;
C r2(0, -1), r3(ratio, 0), r4(0, -ratio), r5(0, 1);
for (int i = 0; i <= (sz >> 1); i++) {
int j = (sz - i) & (sz - 1);
C a1 = (fa[i] + fa[j].conj());
C a2 = (fa[i] - fa[j].conj()) * r2;
C b1 = (fb[i] + fb[j].conj()) * r3;
C b2 = (fb[i] - fb[j].conj()) * r4;
if (i != j) {
C c1 = (fa[j] + fa[i].conj());
C c2 = (fa[j] - fa[i].conj()) * r2;
C d1 = (fb[j] + fb[i].conj()) * r3;
C d2 = (fb[j] - fb[i].conj()) * r4;
fa[i] = c1 * d1 + c2 * d2 * r5;
fb[i] = c1 * d2 + c2 * d1;
}
fa[j] = a1 * b1 + a2 * b2 * r5;
fb[j] = a1 * b2 + a2 * b1;
}
fft(fa, sz);
fft(fb, sz);
vector<T> ret(need);
for (int i = 0; i < need; i++) {
int64_t aa = llround(fa[i].x);
int64_t bb = llround(fb[i].x);
int64_t cc = llround(fa[i].y);
aa = T(aa).x, bb = T(bb).x, cc = T(cc).x;
ret[i] = aa + (bb << 15) + (cc << 30);
}
return ret;
}
};
// 参考（https://nyaannyaan.github.io/library/data-structure-2d/2d-segment-tree.hpp.html)
template <typename T, typename F>
struct SegmentTree2D {
private:
int id(int h, int w) const { return h * 2 * W + w; }
public:
int H, W;
vector<T> seg;
const F f;
const T I;
SegmentTree2D(int h, int w, F _f, const T &i) : f(_f), I(i) { init(h, w); }
void init(int h, int w) {
H = W = 1;
while (H < h) H <<= 1;
while (W < w) W <<= 1;
seg.assign(4 * H * W, I);
}
// build にのみ呼ぶ
void set(int h, int w, const T &x) { seg[id(h + H, w + W)] = x; }
void build() {
// w in [W, 2W)
for (int w = W; w < 2 * W; w++) {
for (int h = H - 1; h; h--) {
seg[id(h, w)] = f(seg[id(2 * h + 0, w)], seg[id(2 * h + 1, w)]);
}
}
// h in [0, 2H)
for (int h = 0; h < 2 * H; h++) {
for (int w = W - 1; w; w--) {
seg[id(h, w)] = f(seg[id(h, 2 * w + 0)], seg[id(h, 2 * w + 1)]);
}
}
}
T get(int h, int w) const { return seg[id(h + H, w + W)]; }
T operator()(int h, int w) const { return seg[id(h + H, w + W)]; }
void update(int h, int w, const T &x) {
h += H, w += W;
seg[id(h, w)] = x;
for (int i = h >> 1; i; i >>= 1) {
seg[id(i, w)] = f(seg[id(2 * i + 0, w)], seg[id(2 * i + 1, w)]);
}
for (; h; h >>= 1) {
for (int j = w >> 1; j; j >>= 1) {
seg[id(h, j)] = f(seg[id(h, 2 * j + 0)], seg[id(h, 2 * j + 1)]);
}
}
}
T _inner_query(int h, int w1, int w2) {
T res = I;
for (; w1 < w2; w1 >>= 1, w2 >>= 1) {
if (w1 & 1) res = f(res, seg[id(h, w1)]), w1++;
if (w2 & 1) --w2, res = f(res, seg[id(h, w2)]);
}
return res;
}
// [ (h1,w1), (h2,w2) ) 半開
T query(int h1, int w1, int h2, int w2) {
if (h1 >= h2 || w1 >= w2) return I;
T res = I;
h1 += H, h2 += H, w1 += W, w2 += W;
for (; h1 < h2; h1 >>= 1, h2 >>= 1) {
if (h1 & 1) res = f(res, _inner_query(h1, w1, w2)), h1++;
if (h2 & 1) --h2, res = f(res, _inner_query(h2, w1, w2));
}
return res;
}
};
/**
* @brief 二次元セグメント木
* @docs docs/data-structure-2d/2d-segment-tree.md
*/
using S = ll;
using S2 = ll;
// 区間取得をどのようにするかを定義する。RMQだったらmin(a,b)とかになる。
S op(S a, S b) { return max(a, b); };
S e() { return -1; }
S op2(S a, S b) { return min(a, b); };
S e2() { return 1e9; }
/* binary_trie
insert(x,w): xをw個追加する。
insert(x,w): xを1個追加する。
erase(x,w): xをw個削除する。
erase(x): xを全て削除する。
search(x):xを個数を調べる
count(): binary_trieにある数字の個数。
at(k): binary_trieのk(0-index)番目に小さい要素の数
count_ress_eq(x): x以下の要素の個数
count_ress(x): x未満の要素の個数
count_upper_eq(x): x以上の要素の個数
count_upper(x): xより大きい要素の個数
erement_ress_eq(x): x以下の要素のうち最大の要素を出力
erement_ress(x): x未満の要素のうち最大の要素を出力
erament_upper_eq(x): x以上の要素のうち最小の要素の出力
eremant_upper(x): xより大きいx以下の要素のうち最大の要素を出力
*/
#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct binary_trie {
struct Node { // 頂点を表す構造体
std::array<int, 2> next; // 子の頂点番号を格納。存在しなければ-1
long long common; // いくつの単語がこの頂点を共有しているか
Node() : common(0) { next.fill(-1); };
};
// (2^depthまでの桁をみる)
vector<Node> nodes; // trie 木本体
int root;
int depth = 60;
binary_trie() : root(0) { nodes.push_back(Node()); }
binary_trie(int dep) : root(0), depth(dep) { nodes.push_back(Node()); }
// 任意の数の数字を追加する
void insert(const T &word, long long number) {
int node_id = 0;
for (int i = depth; i > -1; i--) {
int c = (word >> i) & 1;
// cout << next_id << ' ' << node_id <<'
// '<<nodes[node_id].next.size() <<' ' <<c << endl;
if (nodes[node_id].next.at(c) ==
-1) { // 次の頂点が存在しなければ追加
nodes[node_id].next.at(c) = (int)nodes.size();
nodes.emplace_back(Node());
}
nodes[node_id].common += number;
node_id = nodes[node_id].next.at(c);
;
}
nodes[node_id].common += number;
}
// 数を１個追加する
void insert(const T &word) { insert(word, 1); }
// 削除処理：number個存在するなら削除して、そうでない場合は何もしない)
void erase(const T &word, long long number) {
if (number == 0) return;
int node_id = 0;
stack<int> S;
for (int i = depth; i > -1; i--) {
nodes[node_id].common -= number;
int c = (word >> i) & 1;
if (nodes[node_id].next.at(c) ==
-1) { // 次の頂点が存在しなければ修了
return;
}
node_id = nodes[node_id].next.at(c);
}
nodes[node_id].common -= number;
}
// wordの要素を全削除
void erase(const T &word) { return erase(word, search(word)); }
// 数字の個数の検索
long long search(const T &word) {
int node_id = 0;
for (int i = depth; i > -1; i--) {
int c = (word >> i) & 1;
if (nodes[node_id].next[c] == -1) { // 次の頂点が存在しなければ終了
return 0;
}
node_id = nodes[node_id].next[c];
}
// 0個のノードも存在する
return nodes[node_id].common;
}
// binary_trieに存在する要素の個数
int count() { return nodes[0].common; }
// binary_trieに存在する要素の最大値(要素自体が無ければ-1を出力)
T maximum() {
long long sum = 0;
if (nodes[0].common == 0) return -1;
int node_id = 0;
for (int i = depth; i > -1; i--) {
int next_id = nodes[node_id].next.at(1);
if (next_id != -1) {
if (nodes[next_id].common > 0) {
sum += (1LL << i);
node_id = next_id;
}
} else
node_id = nodes[node_id].next.at(0);
}
return sum;
}
// binary_trieに存在する要素の最小値(要素自体が無ければ-1を出力)
T minimum() {
T sum = 0;
if (nodes[0].common == 0) return -1;
int node_id = 0;
for (int i = depth; i > -1; i--) {
int next_id = nodes[node_id].next.at(0);
if (next_id != -1) {
if (nodes[next_id].common > 0) {
node_id = next_id;
}
} else {
sum += (1LL << i);
node_id = nodes[node_id].at(1);
}
}
return sum;
}
// binary_trieの小さい順からk(0-index)番目の要素(要素自体が無ければ-1を出力)
T at(int k) {
// 範囲外参照した場合-1を出力する。
if (k < 0 || k >= count()) {
return -1;
}
int x = k;
T sum = 0;
int node_id = 0;
for (int i = depth; i > -1; i--) {
int next_id = nodes[node_id].next[0];
if (next_id != -1) {
if (nodes[next_id].common > x) {
node_id = next_id;
} else {
sum += (1LL << i);
node_id = nodes[node_id].next[1];
x -= nodes[next_id].common;
}
} else {
sum += (1LL << i);
node_id = nodes[node_id].next[1];
}
if (node_id == -1) break;
}
return sum;
}
// word以下の要素の数
int count_ress_eq(T word) {
int sum = 0;
int node_id = 0;
for (int i = depth; i > -1; i--) {
int next_id = nodes[node_id].next[0];
// wordのi桁目が1のビットのとき操作を終えた後、i桁目が1であるものに移動する。
if ((word >> i) & 1) {
// i桁目が0の場合、明らかに下回るのでその個数を追加する。
if (next_id != -1) sum += nodes[next_id].common;
node_id = nodes[node_id].next[1];
}
// それ意外の場合、i桁目が0であるものに移動する。
else
node_id = next_id;
if (node_id == -1) {
break;
}
}
// word に等しくなる要素の個数の追加
if (node_id != -1) sum += nodes[node_id].common;
return sum;
}
// word未満の要素の数
int count_ress(T word) {
int sum = 0;
int node_id = 0;
for (int i = depth; i > -1; i--) {
int next_id = nodes[node_id].next[0];
// wordのi桁目が1のビットのとき操作を終えた後、i桁目が1であるものに移動する。
if ((word >> i) & 1) {
// i桁目が0の場合、明らかに下回るのでその個数を追加する。
if (next_id != -1) sum += nodes[next_id].common;
node_id = nodes[node_id].next[1];
}
// それ意外の場合、i桁目が0であるものに移動する。
else
node_id = next_id;
if (node_id == -1) {
break;
}
}
return sum;
}
// word以上の要素の数
int count_upper_eq(const T &word) { return (count() - count_ress(word)); }
// wordよりも大きい要素の数
int count_upper(const T &word) { return count() - count_ress_eq(word); }
// wordよりも小さい要素の中で最大の要素を出力
T erement_ress(const T &word) { return at(count_ress(word) - 1); }
// word以下の要素の中で最大の要素を出力
T erement_ress_eq(const T &word) { return at(count_ress_eq(word) - 1); }
// word以上の要素の中で最小の要素を出力
T erement_upper_eq(const T &word) { return at(count_ress(word)); }
// wordよりも大きい要素の中で最小の要素を出力
T erement_upper(T word) { return at(count_ress_eq(word + 1)); }
T reat(int k) { return at(count() - 1 - k); }
};
vll G;
void solve() {
ll M, N, K;
ll t;
ll a = 0, b, c, d;
ll x = 1;
string S, T;
cin >> N;
ll count = 0;
for (auto u : G) {
count++;
if (binary_search(ALL(G), N - u)) {
ll v = lower_bound(ALL(G), N - u) - G.begin() + 1;
cout << N << ' ' << abs(count * count - v * v) << ' '
<< 2 * count * v << '\n';
return;
}
if (binary_search(ALL(G), N + u)) {
ll v = lower_bound(ALL(G), N + u) - G.begin() + 1;
cout << N << ' ' << abs(count * count - v) << ' ' << 2 * count * v
<< '\n';
return;
}
}
if (N % 2 == 0) {
cout << (N / 2) * (N / 2) - 1 << ' ' << N << ' '
<< (N / 2) * (N / 2) + 1 << '\n';
return;
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cout << fixed << setprecision(50);
ll t;
t = 1;
reps(i, 1, 1e7 + 1) { G.emplace_back(i * i); }
cin >> t;
rep(_, t) solve();
}