結果
| 問題 |
No.3088 XOR = SUM
|
| ユーザー |
 Falcon_
|
| 提出日時 | 2025-04-04 22:44:07 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 462 ms / 2,000 ms |
| コード長 | 28,373 bytes |
| コンパイル時間 | 21,937 ms |
| コンパイル使用メモリ | 265,280 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-04-04 22:44:59 |
| 合計ジャッジ時間 | 42,988 ms |
|
ジャッジサーバーID （参考情報） |
judge6 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 22 |
ソースコード
//give me AC!!!!!!!!!//
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <numeric>
#include <array>
#include <chrono>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
int INF = 1e9 + 7;
long long inf = 45e17 + 11;
int mod = 998244353;
long double PI = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998626034825342117;
typedef pair<long long, long long > P;
struct mint {
int x;
mint(int x = 0) :x((x% mod + mod) % mod) {}
mint operator-() const { return mint(-x); }
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod - a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
mint operator+(const mint a) const { return mint(*this) += a; }
mint operator-(const mint a) const { return mint(*this) -= a; }
mint operator*(const mint a) const { return mint(*this) *= a; }
mint pow(int t) const {
if (!t) return 1;
mint a = pow(t >> 1);
a *= a;
if (t & 1) a *= *this;
return a;
}
mint inv() const { return pow(mod - 2); }
mint& operator/=(const mint a) { return *this *= a.inv(); }
mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
long long modinv(long long a, long long m) {
long long b = m, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
u %= m;
if (u < 0) u += m;
return u;
}
bool IsPrime(int num)
{
if (num < 2) return false;
else if (num == 2) return true;
else if (num % 2 == 0) return false;
for (int i = 3; i * i <= num; i += 2)
{
if (num % i == 0)
{
return false;
}
}
return true;
}
long long gcd(long long a, long long b) {
if (b == 0)return a;
while (a % b != 0) {
long long u = a % b;
a = b;
b = u;
}
return b;
}
long long lcm(long long x, long long y) {
return x / gcd(x, y) * y;
}
const int MAX = 1000010;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++) {
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
long long COM(int n, int k) {
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
vector<int> sieve(int max) {
vector<bool>prime(max + 1, true);
vector<int>A;
for (int i = 2; i <= max; ++i)
if (prime[i]) {
A.push_back(i);
for (int j = 2; i * j <= max; ++j)
prime[i * j] = false;
}
return A;
}
string mmax(string S, string T) {
if (S.size() > T.size())
return S;
if (T.size() > S.size())
return T;
return max(S, T);
};
long long biggcd(vector<long long>& a) {
long long ans = 0;
for (int i = 0; i < a.size(); i++) {
ans = gcd(ans, a[i]);
}
return ans;
}
struct edge {
long long from;
long long to;
long long cost;
};
using Edges = vector<edge>;
void bfsub(const Edges& Es, int s, vector<bool>& B, vector<bool>& d, vector<bool>& f) {
B[s] = true;
for (auto e : Es) {
if (!B[e.to] && d[e.from] && d[e.to] && f[e.from] && f[e.to]) {
B[e.to] = true;
bfsub(Es, e.to, B, d, f);
}
}
}
bool bf(const Edges& Es, int V, int s, vector<long long>& dis, vector<bool>& d) {
dis.resize(V, inf);
d.resize(V, false);
int cnt = 0;
while (cnt < V) {
bool end = true;
for (auto e : Es) {
if (e.from == s && dis[e.to] == inf) {
d[e.from] = true;
dis[e.to] = e.cost;
end = false;
}
if (dis[e.from] != inf && dis[e.from] + e.cost < dis[e.to]) {
d[e.from] = true;
dis[e.to] = dis[e.from] + e.cost;
end = false;
}
}
if (end) break;
cnt++;
}
return (cnt == V);
}
template <typename T>
struct BIT {
int n; // 配列の要素数(数列の要素数+1)
vector<T> bit; // データの格納先
BIT(int n_) : n(n_ + 1), bit(n, 0) {}
// 1-index
void add(int i, T x) {
for (int idx = i; idx < n; idx += (idx & -idx)) {
bit[idx] += x;
}
}
// 1-index
T sum(int i) {
T s(0);
for (int idx = i; idx > 0; idx -= (idx & -idx)) {
s += bit[idx];
}
return s;
}
// [l,r) の区間和を取得
T query(int l, int r) { return sum(r - 1) - sum(l - 1); }
int lower_bound(T w) { // a_1 + a_2 + ... + a_x >= w となるような最小の x を求める(ただし a_i >= 0)
if (w <= 0) {
return 0;
}
else {
int x = 0, r = 1;
while (r < n) r = r << 1;
for (int len = r; len > 0; len = len >> 1) { // 長さlenは1段下るごとに半分に
if (x + len < n && bit[x + len] < w) { // 採用するとき
w -= bit[x + len];
x += len;
}
}
return x + 1;
}
}
};
// vは0以上n-1以下
int count_inversion(vector<int>& v) {
int n = v.size();
BIT<int> bit(n);
int ret = 0;
for (int i = 0; i < n; i++) {
ret += bit.query(v[i] + 1, n + 1);
bit.add(v[i] + 1, 1);
}
return ret;
}
bool bmdfs(vector<bool>& used, vector<vector<int>>& G, vector<int>& match, int v) {
used[v] = true;
for (int i = 0; i < G[v].size(); i++) {
int u = G[v][i], w = match[u];
if (w < 0 || !used[w] && bmdfs(used, G, match, w)) {
match[v] = u;
match[u] = v;
return true;
}
}
return false;
}
int bm(vector<bool>& used, vector<vector<int>>& G, vector<int>& match, int V) {
int res = 0;
for (int i = 0; i < match.size(); i++) {
match[i] = -1;
}
for (int v = 0; v < V; v++) {
if (match[v] < 0) {
for (int i = 0; i < used.size(); i++) {
used[i] = 0;
}
if (bmdfs(used, G, match, v)) {
res++;
}
}
}
return res;
}
long long sttolo(string S) {
long long count = 1000000000ll;
long long ans = 0;
for (int i = 0; i < S.size(); i++) {
if (S[i] == '.') {
count /= 10; continue;
}
if (count == 10000) {
ans *= 10;
}
ans += count * (S[i] - '0');
if (count != 1000000000ll) {
count /= 10;
}
}
return ans;
}
#define rep(i,N) for(int i=0;i<(int)(N);i++)
namespace geometry2d {
/*
for Floating Point Error
*/
constexpr double eps = 1e-10;
/*
a > 0 ... 1
a = 0 ... 0
a < 0 ... -1
*/
constexpr int sgn(const double a) {
return (a < -eps ? -1 : (a > eps ? 1 : 0));
}
struct Point {
double x, y;
Point() = default;
constexpr Point(double _x, double _y) : x(_x), y(_y) {}
double length() const { return std::sqrt(lengthSquare()); }
constexpr double lengthSquare() const noexcept(true) { return dot(*this); }
constexpr double dot(const Point& other) const noexcept(true) { return x * other.x + y * other.y; }
constexpr double cross(const Point& other) const noexcept(true) { return x * other.y - y * other.x; }
double distanceFrom(const Point& other) const noexcept(true) { return (other - *this).length(); }
Point normalized() const { return Point(x / length(), y / length()); }
constexpr bool isZero() const noexcept(true) { return x == 0.0 && y == 0.0; }
Point normalUnitVector() const { return Point(-normalized().y, normalized().x); }
Point rotation(double arg) const {
double cs = std::cos(arg), sn = std::sin(arg);
return Point(x * cs - y * sn, x * sn + y * cs);
}
double angle() const { return std::atan2(y, x); }
constexpr Point operator +() const noexcept(true) { return *this; }
constexpr Point operator -() const noexcept(true) { return Point(-x, -y); }
constexpr Point operator +(const Point& other) const noexcept(true) { return Point(x + other.x, y + other.y); }
constexpr Point operator -(const Point& other) const noexcept(true) { return Point(x - other.x, y - other.y); }
constexpr Point operator *(double s) const noexcept(true) { return Point(x * s, y * s); }
constexpr Point operator /(double s) const noexcept(true) { return Point(x / s, y / s); }
constexpr bool operator ==(const Point& other) const noexcept(true) { return sgn(x - other.x) == 0 && sgn(y - other.y) == 0; }
constexpr bool operator !=(const Point& other) const noexcept(true) { return sgn(x - other.x) || sgn(y - other.y); }
constexpr bool operator <(const Point& other) const noexcept(true) {
if (sgn(x - other.x) != 0) return sgn(x - other.x) < 0;
return sgn(y - other.y) < 0;
}
Point& operator +=(const Point& other) {
x += other.x;
y += other.y;
return *this;
}
Point& operator -=(const Point& other) {
x -= other.x;
y -= other.y;
return *this;
}
Point& operator *=(double s) {
x *= s;
y *= s;
return *this;
}
Point& operator /=(double s) {
x /= s;
y /= s;
return *this;
}
};
constexpr inline Point operator *(double a, const Point& p) { return Point(p.x * a, p.y * a); }
int angletype(const Point& a, const Point& b, const Point& c) {
double v = (a - b).dot(c - b);
return (sgn(v) > 0 ? 0 : sgn(v) < 0 ? 2 : 1);
}
struct Circle {
Point p;
double r;
Circle() = default;
constexpr Circle(Point _p, double _r) : p(_p), r(_r) {}
};
int isIntersect(const Circle& c1, const Circle& c2) {
double d = c1.p.distanceFrom(c2.p);
if (sgn(d - (c1.r + c2.r)) > 0) return 4;
if (sgn(d - (c1.r + c2.r)) == 0) return 3;
if (sgn(d - abs(c1.r - c2.r)) == 0) return 1;
if (sgn(d - abs(c1.r - c2.r)) < 0) return 0;
return 2;
}
std::vector<Point> crossPoint(const Circle& c1, const Circle& c2) {
std::vector<Point> res;
const int mode = isIntersect(c1, c2);
if (mode == 4 || mode == 0) return res;
double d = c1.p.distanceFrom(c2.p);
if (mode == 3) {
double x, y;
x = (c1.r * c2.p.x + c2.r * c1.p.x) / (c1.r + c2.r);
y = (c1.r * c2.p.y + c2.r * c1.p.y) / (c1.r + c2.r);
res.emplace_back(Point(x, y));
return res;
}
if (mode == 1) {
double x, y;
x = (-c2.r * c1.p.x + c1.r * c2.p.x) / (c1.r - c2.r);
y = (-c2.r * c1.p.y + c1.r * c2.p.y) / (c1.r - c2.r);
res.emplace_back(Point(x, y));
return res;
}
double r1cos = (c1.r * c1.r + d * d - c2.r * c2.r) / (2 * d);
double r1sin = std::sqrt(c1.r * c1.r - r1cos * r1cos);
Point vec = Point(c2.p.x - c1.p.x, c2.p.y - c1.p.y);
if (sgn(c1.r - r1cos) == 0) r1sin = 0;
Point e12 = vec.normalized();
Point h12 = vec.normalUnitVector();
res.emplace_back(c1.p + r1cos * e12 + r1sin * h12);
res.emplace_back(c1.p + r1cos * e12 - r1sin * h12);
return res;
}
}
using namespace geometry2d;
void prime_num(vector<int>& factornum) {
for (int i = 0; i < factornum.size(); i++)factornum[i] = 1;
for (int i = 2; i * i < factornum.size(); i++) {
if (factornum[i] == 1) {
for (int j = 2; i * j < factornum.size(); j++) {
factornum[i * j] = factornum[i] + factornum[j];
}
}
}
}
int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
struct ts_edge {
int to;
};
using graph = vector<vector<ts_edge>>;
vector<int> ts(const graph& G) {
vector<int> ans;
int n = (int)G.size();
vector<int> ind(n);
for (int i = 0; i < n; i++) {
for (auto e : G[i]) {
ind[e.to]++;
}
}
queue<int> que;
for (int i = 0; i < n; i++) {
if (ind[i] == 0) {
que.push(i);
}
}
while (!que.empty()) {
int now = que.front();
ans.push_back(now);
que.pop();
for (auto e : G[now]) {
ind[e.to]--;
if (ind[e.to] == 0) {
que.push(e.to);
}
}
}
return ans;
}
/* RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
update(a,b,x): 区間[a,b) の要素を x に更新。O(log(n))
query(a,b): [a,b) での最小の要素を取得。O(log(n))
*/
struct segment_tree {
int n;
vector<int> node;
segment_tree(int n) : n(n), node(n << 1, 0) {} // 初期値が0になりました
// i番目の要素そのものにアクセスできる機能をつけました
int operator[](int i) { return node[i + n]; }
void set(int i, int x) {
node[i += n] = x;
while (i >>= 1) node[i] = node[i << 1 | 0] + node[i << 1 | 1]; // 和になりました
}
int fold(int l, int r) {
int res = 0; // 初期値が0になりました
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = res + node[l++]; // 和になりました
if (r & 1) res = node[--r] + res; // 和になりました
}
return res;
}
};
struct Eratosthenes {
// テーブル
vector<bool> isprime;
// 整数 i を割り切る最小の素数
vector<int> minfactor;
// コンストラクタで篩を回す
Eratosthenes(int N) : isprime(N + 1, true),
minfactor(N + 1, -1) {
// 1 は予めふるい落としておく
isprime[1] = false;
minfactor[1] = 1;
// 篩
for (int p = 2; p <= N; ++p) {
// すでに合成数であるものはスキップする
if (!isprime[p]) continue;
// p についての情報更新
minfactor[p] = p;
// p 以外の p の倍数から素数ラベルを剥奪
for (int q = p * 2; q <= N; q += p) {
// q は合成数なのでふるい落とす
isprime[q] = false;
// q は p で割り切れる旨を更新
if (minfactor[q] == -1) minfactor[q] = p;
}
}
}
// 高速素因数分解
// pair (素因子, 指数) の vector を返す
vector<pair<int, int>> factorize(int n) {
vector<pair<int, int>> res;
while (n > 1) {
int p = minfactor[n];
int exp = 0;
// n で割り切れる限り割る
while (minfactor[n] == p) {
n /= p;
++exp;
}
res.emplace_back(p, exp);
}
return res;
}
// 高速約数列挙
vector<int> divisors(int n) {
vector<int> res({ 1 });
// n を素因数分解 (メンバ関数使用)
auto pf = factorize(n);
// 約数列挙
for (auto p : pf) {
int s = (int)res.size();
for (int i = 0; i < s; ++i) {
int v = 1;
for (int j = 0; j < p.second; ++j) {
v *= p.first;
res.push_back(res[i] * v);
}
}
}
return res;
}
};
struct UnionFind {
vector<int> par, size;
UnionFind(int x) {
par.resize(x);
size.resize(x, 1);
for (int i = 0; i < x; i++) {
par[i] = i;
}
}
int find(int x) {
if (par[x] == x)
return x;
return par[x] = find(par[x]);
}
bool same(int x, int y) {
return find(x) == find(y);
}
int consize(int x) {
return size[find(x)];
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y)
return;
if (size[x] < size[y]) {
par[x] = y;
size[y] += size[x];
}
else {
par[y] = x;
size[x] += size[y];
}
}
};
#define int long long
struct segment_tree_max {
int n;
vector<int> node;
segment_tree_max(int n) : n(n), node(n << 1, inf) {} // 初期値が0になりました
// i番目の要素そのものにアクセスできる機能をつけました
int operator[](int i) { return node[i + n]; }
void set(int i, int x) {
node[i += n] = x;
while (i >>= 1) node[i] = min(node[i << 1 | 0], node[i << 1 | 1]);
}
int fold(int l, int r) {
int res = inf; // 初期値が0になりました
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = min(res, node[l++]); // 和になりました
if (r & 1) res = min(node[--r], res); // 和になりました
}
return res;
}
};
struct Edge {
long long to;
long long cost;
};
using Graph = vector<vector<Edge>>;
/* dijkstra(G,s,dis)
入力：グラフ G, 開始点 s, 距離を格納する dis
計算量：O(|E|log|V|)
副作用：dis が書き換えられる
*/
void dijkstra(const Graph& G, int s, vector<long long>& dis) {
int N = G.size();
dis.resize(N, inf);
priority_queue<P, vector<P>, greater<P>> pq; // 「仮の最短距離, 頂点」が小さい順に並ぶ
dis[s] = 0;
pq.emplace(dis[s], s);
while (!pq.empty()) {
P p = pq.top();
pq.pop();
int v = p.second;
if (dis[v] < p.first) { // 最短距離で無ければ無視
continue;
}
for (auto& e : G[v]) {
if (dis[e.to] > dis[v] + e.cost) { // 最短距離候補なら priority_queue に追加
dis[e.to] = dis[v] + e.cost;
pq.emplace(dis[e.to], e.to);
}
}
}
}
template <typename T>
struct RMQ {
const T INF = numeric_limits<T>::max();
int n;
vector<T> dat, lazy;
RMQ(int n_) : n(), dat(n_ * 4, 0), lazy(n_ * 4, 0) {
int x = 1;
while (n_ > x) x *= 2;
n = x;
}
void set(int i, T x) { dat[i + n - 1] = x; }
void build() {
for (int k = n - 2; k >= 0; k--) dat[k] = min(dat[2 * k + 1], dat[2 * k + 2]);
}
/* lazy eval */
void eval(int k) {
if (lazy[k] == 0) return; // 更新するものが無ければ終了
if (k < n - 1) { // 葉でなければ子に伝搬
lazy[k * 2 + 1] += lazy[k];
lazy[k * 2 + 2] += lazy[k];
}
// 自身を更新
dat[k] += lazy[k];
lazy[k] = 0;
}
void add(int a, int b, T x, int k, int l, int r) {
eval(k);
if (a <= l && r <= b) { // 完全に内側の時
lazy[k] += x;
eval(k);
}
else if (a < r && l < b) { // 一部区間が被る時
add(a, b, x, k * 2 + 1, l, (l + r) / 2); // 左の子
add(a, b, x, k * 2 + 2, (l + r) / 2, r); // 右の子
dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}
void add(int a, int b, T x) { add(a, b, x, 0, 0, n); }
T query_sub(int a, int b, int k, int l, int r) {
eval(k);
if (r <= a || b <= l) { // 完全に外側の時
return INF;
}
else if (a <= l && r <= b) { // 完全に内側の時
return dat[k];
}
else { // 一部区間が被る時
T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
}
T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
T find_rightest(int a, int b, int x) { return find_rightest_sub(a, b, x, 0, 0, n); } // 存在しなければ a-1
T find_leftest(int a, int b, int x) { return find_leftest_sub(a, b, x, 0, 0, n); } // 存在しなければ b
T find_rightest_sub(int a, int b, int x, int k, int l, int r) {
eval(k);
if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1
return a - 1;
}
else if (k >= n - 1) { // 自分が葉ならその位置をreturn
return (k - (n - 1));
}
else {
int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
if (vr != a - 1) { // 右の部分木を見て a-1 以外ならreturn
return vr;
}
else { // 左の部分木を見て値をreturn
return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
}
}
}
T find_leftest_sub(int a, int b, int x, int k, int l, int r) {
eval(k);
if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b
return b;
}
else if (k >= n - 1) { // 自分が葉ならその位置をreturn
return (k - (n - 1));
}
else {
int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
if (vl != b) { // 左の部分木を見て b 以外ならreturn
return vl;
}
else { // 右の部分木を見て値をreturn
return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
}
}
}
/* debug */
inline T operator[](int a) { return query(a, a + 1); }
void print() {
for (int i = 0; i < n; ++i) {
cout << (*this)[i];
if (i != n) cout << ",";
}
cout << endl;
}
};
void wf(vector<vector<long long>>& dist, vector<vector<long long>>& prev) {
int V = dist.size();
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
prev[i][j] = prev[k][j];
}
}
}
}
}
long long power(long long x, long long n) {
long long ret = 1;
while (n > 0) {
if (n & 1) ret = ret * x % mod; // n の最下位bitが 1 ならば x^(2^i) をかける
x = x * x % mod;
n >>= 1; // n を1bit 左にずらす
}
return ret;
}
template< class T >
struct Matrix {
vector< vector< T > > A;
Matrix() {}
Matrix(size_t n, size_t m) : A(n, vector< T >(m, 0)) {}
Matrix(size_t n) : A(n, vector< T >(n, 0)) {};
size_t height() const {
return (A.size());
}
size_t width() const {
return (A[0].size());
}
inline const vector< T >& operator[](int k) const {
return (A.at(k));
}
inline vector< T >& operator[](int k) {
return (A.at(k));
}
static Matrix I(size_t n) {
Matrix mat(n);
for (int i = 0; i < n; i++) mat[i][i] = 1;
return (mat);
}
Matrix& operator+=(const Matrix& B) {
size_t n = height(), m = width();
assert(n == B.height() && m == B.width());
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
(*this)[i][j] += B[i][j];
return (*this);
}
Matrix& operator-=(const Matrix& B) {
size_t n = height(), m = width();
assert(n == B.height() && m == B.width());
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
(*this)[i][j] -= B[i][j];
return (*this);
}
Matrix& operator*=(const Matrix& B)
{
size_t n = height(), m = B.width(), p = width();
assert(p == B.height());
vector<vector<T>> C(n, vector<T>(m, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (int k = 0; k < p; k++)
C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]) % mod;
A.swap(C);
return (*this);
}
Matrix& operator^=(long long k)
{
Matrix B = Matrix::I(height());
while (k > 0)
{
if (k & 1)
B *= *this;
*this *= *this;
k >>= 1LL;
}
A.swap(B.A);
return (*this);
}
Matrix operator+(const Matrix& B) const {
return (Matrix(*this) += B);
}
Matrix operator-(const Matrix& B) const {
return (Matrix(*this) -= B);
}
Matrix operator*(const Matrix& B) const {
return (Matrix(*this) *= B);
}
Matrix operator^(const long long k) const {
return (Matrix(*this) ^= k);
}
friend ostream& operator<<(ostream& os, Matrix& p) {
size_t n = p.height(), m = p.width();
for (int i = 0; i < n; i++) {
os << "[";
for (int j = 0; j < m; j++) {
os << p[i][j] << (j + 1 == m ? "]\n" : ",");
}
}
return (os);
}
T determinant() {
Matrix B(*this);
assert(width() == height());
T ret = 1;
for (int i = 0; i < width(); i++) {
int idx = -1;
for (int j = i; j < width(); j++) {
if (B[j][i] != 0) idx = j;
}
if (idx == -1) return (0);
if (i != idx) {
ret *= -1;
swap(B[i], B[idx]);
}
ret *= B[i][i];
T vv = B[i][i];
for (int j = 0; j < width(); j++) {
B[i][j] /= vv;
}
for (int j = i + 1; j < width(); j++) {
T a = B[j][i];
for (int k = 0; k < width(); k++) {
B[j][k] -= B[i][k] * a;
}
}
}
return (ret);
}
};
pair<long long,long long> solve(long long N) {
long long now = 1LL;
for (int i = 0; i < 62; i++) {
if (N < now) {
long long ans = now / 2LL;
return { ans,N - ans };
}
now *= 2LL;
}
return { 0,0 };
}
signed main()
{
int T; cin >> T;
for (int i = 0; i < T; i++) {
long long N; cin >> N;
pair<long long,long long> ans = solve(N);
long long now = 1LL;
pair<long long, long long>ans_ = { 0, 0 };
for (int j = 0; j < 62; j++) {
if (N < now) {
ans_ = solve(now / 2LL - 1);
break;
}
now *= 2LL;
}
if (ans.second * 2 > ans_.second) {
cout << ans.first << ' ' << ans.second << endl;
}
else {
cout << ans_.first << ' ' << ans_.second << endl;
}
}
}