結果
| 問題 | No.3788 Floor Sum Queries |
| コンテスト | |
| ユーザー |
 2251799813685248
|
| 提出日時 | 2026-11-08 22:24:15 |
| 言語 | C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL) |
| 結果 |
RE
不安定
|
| 実行時間 | - |
| コード長 | 73,132 bytes |
| 記録 | |
| コンパイル時間 | 3,363 ms |
| コンパイル使用メモリ | 425,420 KB |
| 実行使用メモリ | 9,764 KB |
| 平均クエリ数 | 11.22 |
| 最終ジャッジ日時 | 2026-11-08 22:24:24 |
| 合計ジャッジ時間 | 7,539 ms |
|
ジャッジサーバーID （参考情報） |
judge4_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | RE * 1 |
| other | RE * 8 |
ソースコード
// https://github.com/2251799813685248/Competitive-Programming-Library
#include <iostream>
#include <iterator>
#include <ranges>
#include <set>
#include <utility>
#include <string>
#ifndef LIST__HPP_
#define LIST__HPP_
#include <algorithm>
#include <iostream>
#include <cassert>
#include <functional>
#include <utility>
using uint = unsigned int;
using ll = long long;
using namespace std;
template<typename T> concept has_identity = requires (){T();};
template<typename T> concept has_plus_operator = requires (T a, T b){a+b;};
template<typename T> concept has_compare_operator = requires (T a, T b){a < b;};
template<typename T> concept has_equal_operator = requires (T a, T b){a == b; a != b;};
template<typename T>
class list{
public:
using value_type = T;
constexpr list(): sz_(0), max_sz_(0), A(nullptr){}
constexpr list(uint sz): sz_(sz), max_sz_(sz){
if (sz == 0){A = nullptr; return;}
if (sz > 214748367){cerr << "ValueError: too large or negative size" << endl; assert(false);}
A = new T[sz_]{};
if (A == nullptr){cerr << "MomoryError: failed to allocate memory" << endl; assert(false);}
}
constexpr list(uint sz, T elem): sz_(sz), max_sz_(sz){
if (sz == 0){A = nullptr; return;}
if (sz > 2147483647){cerr << "ValueError: too large or negative size" << endl; assert(false);}
A = new T[sz_]{};
if (A == nullptr){cerr << "MemoryError: failed to allocate memory" << endl; assert(false);}
for (int i = 0; i < sz_; i++){
A[i] = elem;
}
}
constexpr list(initializer_list<T> init): sz_(init.size()), max_sz_(init.size()){
A = new T[sz_]{};
if (A == nullptr){cerr << "MemoryError: failed to allocate memory" << endl; assert(false);}
for (int i = 0; i < sz_; i++){
A[i] = *(init.begin()+i);
}
};
// constexpr list<ll>(const range& r){
// if (r.step_ == 0){cerr << "ValueError: step argument must not be zero" << endl; assert(false);}
// if (r.step_ > 0){
// int imax = r.begin_ >= r.end_ ? 0 : (r.end_-r.begin_+r.step_-1)/r.step_;
// sz_ = imax;
// max_sz_ = imax;
// A = new T[sz_]{};
// if (A == nullptr){cerr << "MemoryError: failed to allocate memory" << endl; assert(false);}
// for (int i = 0; i < imax; i++){
// int target = r.begin_+r.step_*i;
// A[i] = target;
// }
// }
// else{
// int imax = r.end_ >= r.begin_ ? 0 : (r.begin_-r.end_-r.step_-1)/(-r.step_);
// sz_ = imax;
// max_sz_ = imax;
// A = new T[sz_]{};
// if (A == nullptr){cerr << "MemoryError: failed to allocate memory" << endl; assert(false);}
// for (int i = 0; i < imax; i++){
// int target = r.begin_+r.step_*i;
// A[i] = target;
// }
// }
// }
constexpr list(const list<T>& other): sz_(other.sz_), max_sz_(other.max_sz_){
A = new T[max_sz_]{};
for (int i = 0; i < sz_; i++){
A[i] = other.A[i];
}
}
constexpr list(list<T>&& other) noexcept : sz_(other.sz_), max_sz_(other.max_sz_){
A = other.A;
other.sz_ = 0;
other.max_sz_ = 0;
other.A = nullptr;
}
constexpr ~list() {
delete[] A;
}
class iterator{
public:
using difference_type = ll;
using value_type = T;
using pointer = T*;
using reference = T&;
using iterator_category = std::random_access_iterator_tag;
iterator() = delete;
constexpr iterator(const list* listptr_init, const int &idx_init): listptr(listptr_init), idx(idx_init){}
inline constexpr value_type& operator* () const {return listptr->A[this->check_idx()];}
inline constexpr value_type* operator->() const {return &listptr->A[this->check_idx()];}
inline constexpr bool operator==(const iterator &other) const {return idx == other.idx;}
inline constexpr bool operator!=(const iterator &other) const {return idx != other.idx;}
inline constexpr bool operator<(const iterator &other) const {return idx < other.idx;}
inline constexpr bool operator>(const iterator &other) const {return idx > other.idx;}
inline constexpr bool operator<=(const iterator &other) const {return idx <= other.idx;}
inline constexpr bool operator>=(const iterator &other) const {return idx >= other.idx;}
inline constexpr iterator operator++(){
this->idx++;
return *this;
}
inline constexpr iterator operator++(int){
iterator temp = *this;
this->idx++;
return temp;
}
inline constexpr iterator operator--(){
this->idx--;
return *this;
}
inline constexpr iterator operator--(int){
iterator temp = *this;
this->idx--;
return temp;
}
inline constexpr iterator& operator+=(int amount){
this->idx += amount;
return *this;
}
inline constexpr iterator operator+(int amount) const {
iterator temp = *this;
temp.idx += amount;
return temp;
}
inline constexpr iterator& operator-=(const int &amount){
this->idx -= amount;
return *this;
}
inline constexpr iterator operator-(const int &amount) const{
iterator temp = *this;
temp.idx -= amount;
return temp;
}
inline constexpr difference_type operator-(const iterator &other) const{
return idx - other.idx;
}
inline constexpr int check_idx() const {
if (idx < 0 || idx >= listptr->sz_){
cerr << "IteratorIndexError: index out of range. current size: " << listptr->sz_ << " target index: " << idx << endl; assert(false);
}
return idx;
}
inline constexpr int check_idx_tolerate_end() const {
if (idx < 0 || idx > listptr->sz_){
cerr << "IteratorIndexError: index out of range(out of end). current size: " << listptr->sz_ << " target index: " << idx << endl; assert(false);
}
return idx;
}
private:
const list* listptr;
int idx;
};
inline constexpr iterator begin(){return iterator(this, 0);}
inline constexpr iterator begin() const {return iterator(this, 0);}
inline constexpr iterator end(){return iterator(this, sz_);}
inline constexpr iterator end() const {return iterator(this, sz_);}
inline constexpr list& operator=(const list& other){
if (this == &other){return *this;}
sz_ = other.sz_;
max_sz_ = other.max_sz_;
delete[] A;
A = new T[max_sz_]{};
for (int i = 0; i < sz_; i++){
A[i] = other.A[i];
}
return *this;
}
inline constexpr list& operator=(list&& other) noexcept {
if (this == &other){return *this;}
delete[] A;
sz_ = other.sz_;
max_sz_ = other.max_sz_;
A = other.A;
other.sz_ = 0;
other.max_sz_ = 0;
other.A = nullptr;
return *this;
}
inline constexpr bool operator==(const list& other) const {
if (sz_ != other.sz_){return false;}
bool res = true;
for (int i = 0; i < sz_; i++){
if (A[i] != other.A[i]){
res = false;
break;
}
}
return res;
}
inline constexpr bool operator!=(const list& other) const {
return !this->operator==(other);
}
inline constexpr bool operator<(const list& other) const {
int lcp_back = 0;
for (int i = 0, sz2 = min(sz_, other.sz_); i < sz2; i++){
if (A[i] != other.A[i]){break;}
lcp_back++;
}
if (lcp_back == sz_ && lcp_back == other.sz_){return false;}
else if (lcp_back == sz_){return true;}
else if (lcp_back == other.sz_){return false;}
else{return A[lcp_back] < other.A[lcp_back];}
}
inline constexpr bool operator<=(const list& other) const {
int lcp_back = 0;
for (int i = 0, sz2 = min(sz_, other.sz_); i < sz2; i++){
if (A[i] != other.A[i]){break;}
lcp_back++;
}
if (lcp_back == sz_ && lcp_back == other.sz_){return true;}
else if (lcp_back == sz_){return true;}
else if (lcp_back == other.sz_){return false;}
else{return A[lcp_back] < other.A[lcp_back];}
}
inline constexpr bool operator>(const list& other) const {return other < *this;}
inline constexpr bool operator>=(const list& other) const {return other <= *this;}
inline constexpr list& operator+=(const list& other){
for (int i = 0, sz2 = other.size(); i < sz2; i++){
append(other.A[i]);
}
return *this;
}
inline constexpr list operator+(const list& other) const {
return list(*this) += other;
}
inline constexpr list& operator+=(const T& val){
append(val);
return *this;
}
inline constexpr list operator+(const T& val) const {
return list(*this) += val;
}
inline constexpr void append(const T& val){
if (sz_ < max_sz_){
A[sz_] = val;
sz_++;
}
else{
if (max_sz_ < 2){max_sz_ = 2;}
else{max_sz_ += max_sz_>>1;}
auto B = new T[max_sz_]{};
B[sz_] = val;
for (int i = 0; i < sz_; i++){B[i] = std::move(A[i]);}
sz_++;
delete[] A;
A = B;
}
}
inline constexpr void append(T&& val){
if (sz_ < max_sz_){
A[sz_] = std::move(val);
sz_++;
}
else{
if (max_sz_ < 2){max_sz_ = 2;}
else{max_sz_ += max_sz_>>1;}
auto B = new T[max_sz_]{};
B[sz_] = std::move(val);
for (int i = 0; i < sz_; i++){B[i] = std::move(A[i]);}
sz_++;
delete[] A;
A = B;
}
}
inline constexpr T pop(){
if (sz_ == 0){cerr << "IndexError: pop from empty list" << endl; assert(false);}
sz_--;
return std::move(A[sz_]);
}
inline constexpr void reserve(uint new_sz){
if (new_sz > 2147483647){cerr << "ValueError: too large or negative size" << endl; assert(false);}
if ((int)new_sz <= max_sz_){return;}
max_sz_ = new_sz;
auto B = new T[new_sz]{};
if (B == nullptr){cerr << "MemoryError: failed to reallocate memory" << endl; assert(false);}
for (int i = 0; i < sz_; i++){B[i] = std::move(A[i]);}
delete[] A;
A = B;
}
inline constexpr void resize(uint new_sz, T elem = T()){
if (new_sz > 2147483647){cerr << "ValueError: too large or negative size" << endl; assert(false);}
if ((int)new_sz <= max_sz_){
while (sz_ > (int)new_sz){pop();}
for (int i = sz_, new_sz_int = new_sz; i < new_sz_int; i++){A[i] = elem;}
sz_ = new_sz;
return;
}
max_sz_ = new_sz + (new_sz >> 1);
auto B = new T[max_sz_]{};
if (B == nullptr){cerr << "MemoryError: failed to reallocate memory" << endl; assert(false);}
for (int i = 0; i < sz_; i++){B[i] = std::move(A[i]);}
for (int i = sz_, new_sz_int = new_sz; i < new_sz_int; i++){B[i] = elem;}
sz_ = new_sz;
delete[] A;
A = B;
}
template <class InputIterator> inline constexpr void assign(InputIterator first, InputIterator last){
reserve(last-first);
while (first != last){append(*first); first++;}
}
inline constexpr void assign(uint n, const T& val){
reserve(n);
sz_ = n;
for (uint i = 0; i < n; i++){
A[i] = val;
}
}
inline constexpr iterator insert(iterator pos, const T& val){
int idx = pos.check_idx();
append(val);
for (int i = idx; i < sz_-1; i++){swap(A[i], A[sz_-1]);}
return pos;
}
// inline constexpr void insert(iterator pos, iterator begin, iterator end)
inline constexpr iterator erase(iterator pos){
int idx = pos.check_idx();
for (int i = idx; i < sz_-1; i++){
swap(A[i], A[i+1]);
}
sz_ -= 1;
return pos;
}
inline constexpr iterator erase(iterator start, iterator end){
int startidx = start.check_idx_tolerate_end(), endidx = end.check_idx_tolerate_end();
if (startidx > endidx){cerr << "IndexError: invalid interval: [start, end) = []" << startidx << ", " << endidx << ")" << endl; assert(false);}
for (int i = startidx; i < endidx; i++){
A[i].~T();
}
if (startidx < endidx){
for (int i = endidx; i < sz_; i++){
swap(A[i+startidx-endidx], A[i]);
}
}
sz_ -= endidx-startidx;
return end;
}
inline constexpr void clear(){sz_ = 0; max_sz_ = 0; delete[] A;}
inline constexpr const T& operator[](int idx) const {
check_and_adjust_idx(idx);
return A[idx];
}
inline constexpr T& operator[](int idx){
check_and_adjust_idx(idx);
return A[idx];
}
inline constexpr T& front(){return (*this)[0];}
inline constexpr const T& front() const {return (*this)[0];}
inline constexpr T& back(){return (*this)[-1];}
inline constexpr const T& back() const {return (*this)[-1];}
inline constexpr list<T> operator[](int left, int right, int step = 1) const {
if (step == 0){cerr << "ValueError: step argument must not be zero" << endl; assert(false);}
if (step > 0){
int imax = left >= right ? 0 : (right-left+step-1)/step;
list<T> B(imax);
for (int i = 0; i < imax; i++){
int target = left+step*i;
if (target < 0 || target >= sz_){cerr << "IndexError: slice index out of range. current size: " << sz_ << " target index: " << target << endl; assert(false);}
B[i] = A[target];
}
return std::move(B);
}
else{
int imax = right >= left ? 0 : (left-right-step-1)/(-step);
list<T> B(imax);
for (int i = 0; i < imax; i++){
int target = left+step*i;
if (target < 0 || target >= sz_){cerr << "IndexError: slice index out of range. current size: " << sz_ << " target index: " << target << endl; assert(false);}
B[i] = A[target];
}
return std::move(B);
}
}
inline constexpr T* data() {return empty() ? nullptr : &A[0];}
inline constexpr const T* data() const {return empty() ? nullptr : &A[0];}
inline constexpr T sum() const requires has_plus_operator<T> && has_identity<T>{
auto res = T();
for (int i = 0; i < sz_; i++){
res += A[i];
}
return res;
}
template<typename U> inline constexpr U sum(U init) const requires has_plus_operator<T>{
for (int i = 0; i < sz_; i++){
init += A[i];
}
return init;
}
inline constexpr void sort() requires has_compare_operator<T> {
std::sort(begin(), end());
}
inline constexpr void sort_reverse() requires has_compare_operator<T> {
std::sort(begin(), end(), std::move([](const T& a, const T& b){return b < a;}));
}
inline constexpr void sort(const function<bool(T,T)>& f){
std::sort(begin(), end(), f);
}
inline constexpr void reverse(){
std::reverse(begin(), end());
}
inline constexpr ll count(const T& val){
ll res = 0;
for (int i = 0; i < sz_; i++){res += A[i] == val;}
return res;
}
inline constexpr void apply(const function<T(T)>& f){for (int i = 0; i < sz_; i++){A[i] = f(A[i]);}}
inline constexpr list<pair<int, T>> RLE(){
list<pair<int, T>> res;
for (int l = 0, r = 0; l < sz_;){
while (r < sz_ && A[l] == A[r]){
r++;
}
res.append(make_pair(r-l, A[l]));
l = r;
}
return res;
}
inline constexpr iterator lower_bound(const T& val) const requires has_compare_operator<T> {return std::lower_bound(begin(), end(), val);}
inline constexpr iterator upper_bound(const T& val) const requires has_compare_operator<T> {return std::upper_bound(begin(), end(), val);}
inline constexpr ll size() const {return sz_;}
inline constexpr ll maxsize() const {return max_sz_;}
inline constexpr bool empty() const {return sz_ == 0;}
private:
inline constexpr void check_and_adjust_idx(int& idx) const {
if (idx >= sz_){cerr << "IndexError: index out of range. current size: " << sz_ << " target index: " << idx << endl; assert(false);}
if (idx < 0){
if (idx < -sz_){cerr << "IndexError: index out of range. current size: " << sz_ << " target index: " << idx << endl; assert(false);}
idx += sz_;
}
}
int sz_;
int max_sz_;
T* A;
};
#endif /* LIST__HPP_ */
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
#include <functional>
#include <random>
#include <bitset>
#include <chrono>
#include <immintrin.h>
// #include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using ll = long long;
using lll = __int128_t;
using ull = unsigned long long;
#ifdef BOOST_VERSION
using bll = boost::multiprecision::cpp_int;
#endif
using ld = long double;
using pii = array<int,2>;
using pll = array<ll,2>;
using plll = array<lll,2>;
using tll = array<ll,3>;
#define vall(A) A.begin(), A.end()
template<typename T> inline bool btest(T K, int i){return K&(1ull<<i);}
#ifndef LEN_DEFINED
#define LEN_DEFINED
template<typename T> inline constexpr ll len(const T& A){return ssize(A);}
#endif
constexpr ll pow2ll[63] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904};
constexpr ll pow10ll[19] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
constexpr ll di[4] = {0,1,0,-1};
constexpr ll di8[8] = {0,1,1,1,0,-1,-1,-1};
constexpr ll dj[4] = {1,0,-1,0};
constexpr ll dj8[8] = {1,1,0,-1,-1,-1,0,1};
#ifndef FASTIO__HPP_
#define FASTIO__HPP_
#include <array>
#include <bit>
#include <charconv>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <string>
#include <string_view>
#include <tuple>
#include <type_traits>
#include <utility>
// C++20. Integer input must fit the destination type. For modint input, the
// magnitude must fit uint64_t; negative values are reduced modulo the modulus.
// FILE* is borrowed: it must outlive the reader/writer. Do not mix buffered
// readers on one stream. The default input buffer is intended for batch judges;
// interactive programs need BasicInput<1> and explicit output flush().
namespace fastio {
namespace detail {
template<class T> inline constexpr bool integer = std::is_integral_v<T>;
template<class T> struct unsigned_type { using type = std::make_unsigned_t<T>; };
template<> struct unsigned_type<bool> { using type = unsigned char; };
#if defined(__SIZEOF_INT128__)
template<> inline constexpr bool integer<__int128_t> = true;
template<> inline constexpr bool integer<__uint128_t> = true;
template<> struct unsigned_type<__int128_t> { using type = __uint128_t; };
template<> struct unsigned_type<__uint128_t> { using type = __uint128_t; };
#endif
template<class T> using unsigned_t = typename unsigned_type<T>::type;
template<class T> inline constexpr bool signed_integer = integer<T> && T(-1) < T(0);
template<class T> concept modular = requires(T x) { x.val; } &&
(requires { T::mod_value; } || requires { T::mod(); });
template<class T> concept fraction = requires(T x) { x.denominator; };
template<class T> constexpr auto modulus() {
if constexpr (requires { T::mod_value; }) return T::mod_value;
else return T::mod();
}
template<class T> concept indexed_range = requires(T& x) { std::size(x); x[0]; };
template<class T> concept tuple_like = requires { std::tuple_size<T>::value; };
template<class> inline constexpr bool unsupported = false;
inline constexpr auto digit_pairs = [] {
std::array<char, 200> result{};
for (int i = 0; i < 100; ++i) {
result[2*i] = char('0'+i/10);
result[2*i+1] = char('0'+i%10);
}
return result;
}();
inline constexpr auto digit_quads = [] {
std::array<std::array<char,4>,10000> result{};
for (unsigned i = 0; i < 10000; ++i) {
result[i] = {char('0'+i/1000),char('0'+i/100%10),
char('0'+i/10%10),char('0'+i%10)};
}
return result;
}();
inline char* leading_quad(char* p, unsigned value) {
if (value >= 1000) { std::memcpy(p,digit_quads[value].data(),4); return p+4; }
if (value >= 100) { *p++ = char('0'+value/100); value %= 100; }
else if (value < 10) { *p++ = char('0'+value); return p; }
std::memcpy(p,digit_pairs.data()+2*value,2);
return p+2;
}
inline char* decimal32(char* p, std::uint32_t value) {
if (value >= 100000000) {
p = leading_quad(p,value/100000000);
value %= 100000000;
std::memcpy(p,digit_quads[value/10000].data(),4);
std::memcpy(p+4,digit_quads[value%10000].data(),4);
return p+8;
}
if (value >= 10000) {
p = leading_quad(p,value/10000);
std::memcpy(p,digit_quads[value%10000].data(),4);
return p+4;
}
return leading_quad(p,value);
}
template<class T> inline constexpr bool output32 = [] {
if constexpr (integer<T>) return sizeof(T) <= 4 && !std::is_same_v<T,char>;
else if constexpr (modular<T>) return integer<decltype(T{}.val)> && sizeof(T{}.val) <= 4;
else return false;
}();
template<class T> inline char* decimal_small(char* p, const T& value) {
if constexpr (modular<T>) return decimal_small(p,value.val);
else {
std::uint32_t u = static_cast<std::uint32_t>(value);
if constexpr (signed_integer<T>) {
if (value < 0) { *p++ = '-'; u = 0-u; }
}
return decimal32(p,u);
}
}
} // namespace detail
template<std::size_t BufferSize = 1 << 18>
class BasicInput {
static_assert(BufferSize > 0);
std::FILE* file_;
char buffer_[BufferSize+1];
std::size_t position_ = 0, size_ = 0;
bool good_ = true;
int peek() {
if (position_ == size_) {
size_ = std::fread(buffer_, 1, BufferSize, file_);
buffer_[size_] = '\0';
position_ = 0;
if (size_ == 0) return EOF;
}
return static_cast<unsigned char>(buffer_[position_]);
}
int skip_space() {
int c;
while ((c = peek()) != EOF && c <= ' ') ++position_;
return c;
}
template<class U, bool SingleBlock = false> bool magnitude(U& value, bool& negative) {
int c = skip_space();
if (c == EOF) return false;
negative = c == '-';
if (c == '-' || c == '+') { ++position_; c = peek(); }
if (static_cast<unsigned>(c-'0') > 9) return false;
value = 0;
do {
const char* p = buffer_+position_;
if constexpr (sizeof(U) >= 4 && std::endian::native == std::endian::little) {
while (buffer_+size_-p >= 8) {
std::uint64_t block;
std::memcpy(&block,p,8);
// All eight bytes must be ASCII decimal digits.
if (((block+0x4646464646464646ULL) | (block-0x3030303030303030ULL)) & 0x8080808080808080ULL) break;
block -= 0x3030303030303030ULL;
block = (block*10+(block>>8)) & 0x00ff00ff00ff00ffULL;
block = (block*100+(block>>16)) & 0x0000ffff0000ffffULL;
block = (block*10000+(block>>32)) & 0xffffffffULL;
value = value*100000000+static_cast<std::uint32_t>(block);
p += 8;
if constexpr (SingleBlock || sizeof(U) == 4) break;
}
}
unsigned digit;
// The sentinel stops this loop without an EOF/buffer check for
// every digit. Only a token crossing a refill needs the outer loop.
while ((digit = static_cast<unsigned>(static_cast<unsigned char>(*p)-'0')) <= 9) {
value = value*10+digit;
++p;
}
position_ = static_cast<std::size_t>(p-buffer_);
if (position_ != size_) break;
c = peek();
} while (static_cast<unsigned>(c-'0') <= 9);
return true;
}
template<class T> bool read_one(T& value) {
if constexpr (std::is_same_v<T, char>) {
const int c = skip_space();
if (c == EOF) return false;
value = static_cast<char>(c);
++position_;
return true;
} else if constexpr (detail::integer<T>) {
detail::unsigned_t<T> u;
bool negative;
if (!magnitude(u,negative)) return false;
if constexpr (detail::signed_integer<T>) {
// Never negate the minimum signed value, even for int128.
value = negative && u != 0 ? -static_cast<T>(u-1)-1 : static_cast<T>(u);
} else {
if (negative || (std::is_same_v<T,bool> && u > 1)) return false;
value = static_cast<T>(u);
}
return true;
} else if constexpr (detail::modular<T>) {
std::uint64_t u;
bool negative;
// Most modular coefficients have at most ten digits. After the
// first eight, parse the short tail without another wide probe.
if (!magnitude<std::uint64_t,true>(u,negative)) return false;
const auto mod = detail::modulus<T>();
if (u >= mod) u %= mod;
value.val = negative && u != 0 ? mod-u : u;
return true;
} else if constexpr (std::is_same_v<T,std::string>) {
int c = skip_space();
if (c == EOF) return false;
value.clear();
do {
value.push_back(static_cast<char>(c));
++position_;
c = peek();
} while (c != EOF && c > ' ');
return true;
} else if constexpr (std::is_floating_point_v<T>) {
std::string token;
if (!read_one(token)) return false;
const char* first = token.data();
const char* last = first+token.size();
if (first != last && *first == '+') ++first;
const auto result = std::from_chars(first,last,value);
return result.ec == std::errc{} && result.ptr == last;
} else if constexpr (detail::indexed_range<T>) {
const auto n = std::size(value);
if constexpr (requires { std::data(value); }) {
auto* data = std::data(value);
for (decltype(std::size(value)) i = 0; i < n; ++i)
if (!read_one(data[i])) return false;
} else {
for (decltype(std::size(value)) i = 0; i < n; ++i)
if (!read_one(value[i])) return false;
}
return true;
} else if constexpr (detail::tuple_like<T>) {
return std::apply([&](auto&... x) { return (read_one(x) && ...); },value);
} else {
static_assert(detail::unsupported<T>, "Unsupported fastio input type");
}
}
public:
explicit BasicInput(std::FILE* file = stdin) : file_(file) {}
BasicInput(const BasicInput&) = delete;
BasicInput& operator=(const BasicInput&) = delete;
template<class... T> bool read(T&... values) {
if (!good_) return false;
return good_ = (read_one(values) && ...);
}
template<class T> BasicInput& operator>>(T& value) { read(value); return *this; }
explicit operator bool() const { return good_; }
};
template<std::size_t BufferSize = 1 << 18>
class BasicOutput {
static_assert(BufferSize > 0);
std::FILE* file_;
char buffer_[BufferSize];
std::size_t size_ = 0;
bool good_ = true;
bool drain() {
if (!good_) return false;
std::size_t done = 0;
while (done < size_) {
const auto n = std::fwrite(buffer_+done,1,size_-done,file_);
if (n == 0) { size_ = 0; return good_ = false; }
done += n;
}
size_ = 0;
return true;
}
bool put(char c) {
if (!good_ || (size_ == BufferSize && !drain())) return false;
buffer_[size_++] = c;
return true;
}
bool bytes(const char* data, std::size_t count) {
if (!good_) return false;
while (count != 0) {
if (size_ == BufferSize && !drain()) return false;
const auto room = BufferSize-size_;
const auto n = count < room ? count : room;
std::memcpy(buffer_+size_,data,n);
size_ += n; data += n; count -= n;
}
return true;
}
template<class U> bool unsigned_number(U value, bool negative) {
if constexpr (sizeof(U) <= 4 && BufferSize >= 12) {
if (!good_ || (BufferSize-size_ < 12 && !drain())) return false;
char* p = buffer_+size_;
if (negative) *p++ = '-';
p = detail::decimal32(p,value);
size_ = static_cast<std::size_t>(p-buffer_);
return true;
}
// 128-bit unsigned integers need at most 39 decimal digits.
char digits[3*sizeof(U)+2];
char* const end = digits+sizeof(digits);
char* p = end;
while (value >= 100) {
const U q = value/100;
const unsigned r = static_cast<unsigned>(value-q*100);
p -= 2;
std::memcpy(p,detail::digit_pairs.data()+2*r,2);
value = q;
}
if (value < 10) *--p = char('0'+static_cast<unsigned>(value));
else {
p -= 2;
std::memcpy(p,detail::digit_pairs.data()+2*static_cast<unsigned>(value),2);
}
if (negative) *--p = '-';
if constexpr (BufferSize >= sizeof(digits)) {
if (!good_ || (BufferSize-size_ < sizeof(digits) && !drain())) return false;
auto count = static_cast<std::size_t>(end-p);
char* dest = buffer_+size_;
size_ += count;
// Constant-size copies avoid a library call per integer. Each copy
// stays inside the initialized digits and the reserved buffer area.
if constexpr (sizeof(digits) >= 8)
while (count >= 8) {
std::memcpy(dest,p,8);
dest += 8; p += 8; count -= 8;
}
if (count >= 4) { std::memcpy(dest,p,4); dest += 4; p += 4; count -= 4; }
if (count >= 2) { std::memcpy(dest,p,2); dest += 2; p += 2; count -= 2; }
if (count) *dest = *p;
return true;
}
return bytes(p,static_cast<std::size_t>(end-p));
}
template<class T> bool write_one(const T& value) {
if constexpr (std::is_same_v<T,char>) {
return put(value);
} else if constexpr (detail::integer<T>) {
using U = detail::unsigned_t<T>;
U u = static_cast<U>(value);
bool negative = false;
if constexpr (detail::signed_integer<T>) {
negative = value < 0;
if (negative) u = U(0)-u;
}
return unsigned_number(u,negative);
} else if constexpr (detail::modular<T>) {
return write_one(value.val);
} else if constexpr (detail::fraction<T>) {
return write_one(value.numerator) && write_one("/") && write_one(value.denominator);
} else if constexpr (std::is_convertible_v<const T&,std::string_view>) {
const std::string_view text(value);
return bytes(text.data(),text.size());
} else if constexpr (std::is_floating_point_v<T>) {
char text[128];
const auto result = std::to_chars(text,text+sizeof(text),value);
if (result.ec != std::errc{}) return false;
return bytes(text,static_cast<std::size_t>(result.ptr-text));
} else if constexpr (detail::indexed_range<const T>) {
const auto n = std::size(value);
using Element = std::remove_cvref_t<decltype(value[0])>;
if constexpr (detail::indexed_range<Element> || detail::tuple_like<Element>){
for (decltype(std::size(value)) i = 0; i < n; ++i) {
if (i != 0 && !put('\n')) return false;
if (!write_one(value[i])) return false;
}
return true;
}
if constexpr (BufferSize >= 32 && detail::output32<Element> && requires { std::data(value); }) {
const auto* data = std::data(value);
char* p = buffer_+size_;
for (decltype(std::size(value)) i = 0; i < n; ++i) {
if (buffer_+BufferSize-p < 12) {
size_ = static_cast<std::size_t>(p-buffer_);
if (!drain()) return false;
p = buffer_;
}
if (i != 0) *p++ = ' ';
p = detail::decimal_small(p,data[i]);
}
size_ = static_cast<std::size_t>(p-buffer_);
return true;
}
for (decltype(std::size(value)) i = 0; i < n; ++i) {
if (i != 0 && !put(' ')) return false;
if (!write_one(value[i])) return false;
}
return true;
} else if constexpr (detail::tuple_like<T>) {
[[maybe_unused]] bool first = true;
return std::apply([&](const auto&... x) {
return (((std::exchange(first,false) || put(' ')) && write_one(x)) && ...);
},value);
} else {
static_assert(detail::unsupported<T>, "Unsupported fastio output type");
}
}
public:
explicit BasicOutput(std::FILE* file = stdout) : file_(file) {}
BasicOutput(const BasicOutput&) = delete;
BasicOutput& operator=(const BasicOutput&) = delete;
~BasicOutput() { flush(); }
// write concatenates its arguments; print separates them with spaces and
// appends a newline. Ranges and tuples use spaces between their elements.
template<class... T> bool write(const T&... values) {
if (!good_) return false;
return good_ = (write_one(values) && ...);
}
template<class... T> bool print(const T&... values) {
if (!good_) return false;
[[maybe_unused]] bool first = true;
good_ = (((std::exchange(first,false) || put(' ')) && write_one(values)) && ...);
return good_ && put('\n');
}
template<class... T> bool printflush(const T&... values) {
if (!good_) return false;
[[maybe_unused]] bool first = true;
good_ = (((std::exchange(first,false) || put(' ')) && write_one(values)) && ...);
return good_ && put('\n') && flush();
}
bool flush() { return drain() && (good_ = std::fflush(file_) == 0); }
template<class T> BasicOutput& operator<<(const T& value) { write(value); return *this; }
explicit operator bool() const { return good_; }
};
#ifdef LOCAL_a1073741824
using FastInput = BasicInput<1>;
#else
using FastInput = BasicInput<>;
#endif
using FastOutput = BasicOutput<>;
// template<class... T> bool read(T&... values) { return in.read(values...); }
// template<class... T> bool write(const T&... values) { return out.write(values...); }
// template<class... T> bool print(const T&... values) { return out.print(values...); }
// template<class... T> bool printflush(const T&... values) { return out.print(values...) && out.flush(); }
// inline bool flush() { return out.flush(); }
} // namespace fastio
#endif /* FASTIO__HPP_ */
fastio::BasicInput<1> in;
fastio::BasicOutput<1> out;
#define cin do_not_use_cin
template<class... T> bool read(T&... values) { return in.read(values...); }
template<class... T> bool write(const T&... values) { return out.write(values...); }
template<class... T> bool print(const T&... values) { return out.print(values...); }
template<class... T> bool printflush(const T&... values) { return out.print(values...) && out.flush(); }
inline bool flush() { return out.flush(); }
constexpr ll mod = 998244353;
#ifndef MODINT__HPP_
#define MODINT__HPP_
#include <iostream>
#ifndef MATH_FUNCTION_HPP_
#define MATH_FUNCTION_HPP_
#include <array>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using ulll = __uint128_t;
#ifdef BOOST_VERSION
using bll = boost::multiprecision::cpp_int;
#endif
constexpr ll getdigit(ull x){
if (x < 1000000000){
if (x < 100000){
return x == 0 ? 0 : x < 10 ? 1 : x < 100 ? 2 : x < 1000 ? 3 : x < 10000 ? 4 : 5;
}
else{
return x < 1000000 ? 6 : x < 10000000 ? 7 : x < 100000000 ? 8 : 9;
}
}
else{
if (x < 100000000000000){
return x < 10000000000 ? 10 : x < 100000000000 ? 11 : x < 1000000000000 ? 12 : x < 10000000000000 ? 13 : 14;
}
else{
return x < 1000000000000000 ? 15 : x < 10000000000000000 ? 16 : x < 100000000000000000 ? 17 : x < 1000000000000000000 ? 18 : x < 10000000000000000000u ? 19 : 20;
}
}
}
/// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる
constexpr ll modpow(ll a, ull b, const ll m){
ll t = a%m;
ll ans = (m == 1 ? 0 : 1);
while (b > 0){
if (b&1){
ans = (ans*t)%m;
}
b >>= 1;
t = (t*t)%m;
}
return ans;
}
/// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる。mはコンパイル時に決定している必要がある
template<ll m> constexpr ll modpow(ll a, ull b){
ll t = a%m;
ll ans = (m == 1 ? 0 : 1);
while (b > 0){
if (b&1){
ans = (ans*t)%m;
}
b >>= 1;
t = (t*t)%m;
}
return ans;
}
/// @brief a^nを返す。bに関して対数時間で計算できる。
template<typename T> constexpr T powll(T a, T n){
T t = a;
T ans = 1;
while (n > 0){
if (n%2){
ans *= t;
}
n >>= 1;
t *= t;
}
return ans;
}
/// @brief a^nを返す。bに関して対数時間で計算できる
template<> constexpr ll powll(ll a, ll n){
ll t = a;
ll ans = 1;
while (n > 0){
if (n&1){
ans *= t;
}
n >>= 1;
t *= t;
}
return ans;
}
/// @brief floor(sqrt(N))を返す。1.5×10^19まで対応
constexpr ll isqrt(ull N){
assert(N <= 15000000000000000000ull);
ull ret = sqrt(N);
while (ret*ret > N){
ret--;
}
while ((ret+1)*(ret+1) <= N){
ret++;
}
return ret;
}
#ifdef BOOST_VERSION
/// @brief floor(sqrt(N))を返す。多倍長整数に対応
constexpr bll isqrt_large(bll N){
bll ret = sqrt(N);
while (ret*ret > N){
ret--;
}
while ((ret+1)*(ret+1) <= N){
ret++;
}
return ret;
}
#endif
/// @brief floor(log_a(L))を返す
constexpr ll ilog(ll a, ll L){
__int128_t t = 1;
ll ans = 0;
while (t <= L){
ans++;
t *= a;
}
return ans-1;
}
/// @brief 有理数のfloorを求める。 floor(y/x)
template<typename T> constexpr inline T floor2(T y, T x){
if ((x^y) > 0){
x = x > 0 ? x : -x;
y = y > 0 ? y : -y;
return y/x;
}
else if ((x^y) < 0){
x = x > 0 ? x : -x;
y = y > 0 ? y : -y;
return -((y+x-1)/x);
}
else{
return y/x;
}
}
/// @brief 有理数のceilを求める。 ceil(y/x)
template<typename T> constexpr inline T ceil2(T y, T x){
if ((x^y) > 0){
x = x > 0 ? x : -x;
y = y > 0 ? y : -y;
return (y+x-1)/x;
}
else if ((x^y) < 0){
x = x > 0 ? x : -x;
y = y > 0 ? y : -y;
return -(y/x);
}
else{
return y/x;
}
}
/// @brief 一次不定方程式ax+by=gcd(a,b)の解を1つ見つける
/// @param a `a>=0`である必要がある
/// @param b `b>=0`である必要がある
/// @return {x,y,gcd(a,b)}
template<typename T>
constexpr array<T,3> axby1(T a, T b){
T x = 1, y = 0;
T z = 0, w = 1;
T tmp = 0;
while (b){
T p = a/b, q = a%b;
tmp = x - y * p; x = y; y = tmp;
tmp = z - w * p; z = w; w = tmp;
a = b; b = q;
}
return {x, z, a};
}
/// @brief 1/a mod Mを求める
template<typename T, typename U>
constexpr T inverse_mod(T a, U M){
auto temp = axby1(a,(T)M);
assert(temp[2] == 1);
return (M+temp[0])%M;
}
/// @brief sqrt(a) mod Mを求める。ないなら-1が返される。
template<ll M>
inline constexpr ll cipolla(ll a){
a %= M;
if (M == 2) return a;
if (a == 0) return 0;
ll z = (M-1)/2;
if (modpow<M>(a, z) != 1){return -1;}
int b = 0;
while (modpow<M>((b*b+M-a)%M, z) == 1){
b++;
}
array<ll,2> x{1,0};
array<ll,2> y{b, 1};
ll w = (b*b+M-a)%M;
z++;
while (z){
if (z&1){
ll temp = x[0];
x[0] = x[0]*y[0]%M+x[1]*y[1]%M*w%M;
if (x[0] >= M){x[0] -= M;}
x[1] = temp*y[1]%M+x[1]*y[0]%M;
if (x[1] >= M){x[1] -= M;}
}
ll temp = y[0];
y[0] = y[0]*y[0]%M+y[1]*y[1]%M*w%M;
if (y[0] >= M){y[0] -= M;}
y[1] = 2*temp*y[1]%M;
z >>= 1;
}
return x[0];
}
inline constexpr ll cipolla(ll a, const ll M){
a %= M;
if (M == 2) return a;
if (a == 0) return 0;
ll z = (M-1)/2;
if (modpow(a, z, M) != 1){return -1;}
int b = 0;
while (modpow((b*b+M-a)%M, z, M) == 1){
b++;
}
array<ll,2> x{1,0};
array<ll,2> y{b, 1};
ll w = (b*b+M-a)%M;
z++;
while (z){
if (z&1){
ll temp = x[0];
x[0] = x[0]*y[0]%M+x[1]*y[1]%M*w%M;
if (x[0] >= M){x[0] -= M;}
x[1] = temp*y[1]%M+x[1]*y[0]%M;
if (x[1] >= M){x[1] -= M;}
}
ll temp = y[0];
y[0] = y[0]*y[0]%M+y[1]*y[1]%M*w%M;
if (y[0] >= M){y[0] -= M;}
y[1] = 2*temp*y[1]%M;
z >>= 1;
}
return x[0];
}
/// @brief x以下の最大の2冪を返す。0は0が返る。
inline constexpr ull lowerpow2(ull x){
if (x == 0){return 0;}
return 1ull<<(63-__builtin_clzll(x));
}
/// @brief x以上の最小の2冪を返す。0は0が返る。
inline constexpr ull upperpow2(ull x){
if (x == 0){return 0;}
if (x == 1){return 1;}
return 1ull<<(64-__builtin_clzll(x-1));
}
/// @brief xのpopcountを求める
inline constexpr int popcount(ull x){
return __builtin_popcountll(x);
}
/// @brief xのbit lengthを求める。
inline constexpr int bit_length(ull x){
if (x == 0){return 0;}
return 64-__builtin_clzll(x);
}
#endif /* MATH_FUNCTION_HPP_ */
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using namespace std;
template <uint M>
struct constant_modint {
static constexpr uint mod_value = M;
uint val;
constant_modint() : val(0) {}
template <class T> constant_modint(T x) {
ll y = (ll)(x % (ll)M);
if (y < 0) y += M;
val = y;
}
constant_modint& operator+=(const constant_modint& rhs) {
val += rhs.val;
if (val >= M) val -= M;
return *this;
}
constant_modint& operator-=(const constant_modint& rhs) {
if (val < rhs.val) val += M;
val -= rhs.val;
return *this;
}
constant_modint& operator*=(const constant_modint& rhs) {
val = (ull)val * rhs.val % M;
return *this;
}
constant_modint& operator/=(const constant_modint& rhs) {
return *this *= rhs.inv();
}
constant_modint operator+() const { return *this; }
constant_modint operator-() const { return constant_modint(0) - *this; }
friend constant_modint operator+(const constant_modint& lhs, const constant_modint& rhs) { return constant_modint(lhs) += rhs; }
friend constant_modint operator-(const constant_modint& lhs, const constant_modint& rhs) { return constant_modint(lhs) -= rhs; }
friend constant_modint operator*(const constant_modint& lhs, const constant_modint& rhs) { return constant_modint(lhs) *= rhs; }
friend constant_modint operator/(const constant_modint& lhs, const constant_modint& rhs) { return constant_modint(lhs) /= rhs; }
friend bool operator==(const constant_modint& lhs, const constant_modint& rhs) { return lhs.val == rhs.val; }
friend bool operator!=(const constant_modint& lhs, const constant_modint& rhs) { return lhs.val != rhs.val; }
constant_modint pow(ull n) const {
constant_modint res = 1, a = *this;
while (n) {
if (n&1) res *= a;
a *= a;
n >>= 1;
}
return res;
}
constant_modint inv() const {
return inverse_mod<ll,ll>(val, M);
}
friend std::ostream& operator<<(std::ostream& os, const constant_modint& m) {
return os << m.val;
}
friend std::istream& operator>>(std::istream& is, constant_modint& m) {
ll x;
is >> x;
m = constant_modint(x);
return is;
}
};
template <int id = -1>
struct dynamic_modint {
uint val;
static uint& mod() {
static uint M = 998244353;
return M;
}
static void set_mod(uint m) {
mod() = m;
}
dynamic_modint() : val(0) {}
template <class T> dynamic_modint(T x) {
ll y = x % (ll)mod();
if (y < 0) y += mod();
val = (uint)y;
}
dynamic_modint& operator+=(const dynamic_modint& rhs) {
val += rhs.val;
if (val >= mod()) val -= mod();
return *this;
}
dynamic_modint& operator-=(const dynamic_modint& rhs) {
if (val < rhs.val) val += mod();
val -= rhs.val;
return *this;
}
dynamic_modint& operator*=(const dynamic_modint& rhs) {
val = (ull)val * rhs.val % mod();
return *this;
}
dynamic_modint& operator/=(const dynamic_modint& rhs) {
return *this *= rhs.inv();
}
dynamic_modint operator+() const { return *this; }
dynamic_modint operator-() const { return dynamic_modint(0) - *this; }
friend dynamic_modint operator+(const dynamic_modint& lhs, const dynamic_modint& rhs) { return dynamic_modint(lhs) += rhs; }
friend dynamic_modint operator-(const dynamic_modint& lhs, const dynamic_modint& rhs) { return dynamic_modint(lhs) -= rhs; }
friend dynamic_modint operator*(const dynamic_modint& lhs, const dynamic_modint& rhs) { return dynamic_modint(lhs) *= rhs; }
friend dynamic_modint operator/(const dynamic_modint& lhs, const dynamic_modint& rhs) { return dynamic_modint(lhs) /= rhs; }
friend bool operator==(const dynamic_modint& lhs, const dynamic_modint& rhs) { return lhs.val == rhs.val; }
friend bool operator!=(const dynamic_modint& lhs, const dynamic_modint& rhs) { return lhs.val != rhs.val; }
dynamic_modint pow(ull n) const {
dynamic_modint res = 1, a = *this;
while (n) {
if (n & 1) res *= a;
a *= a;
n >>= 1;
}
return res;
}
dynamic_modint inv() const {
ll a = val, b = mod(), u = 1, v = 0;
while (b) {
ll t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
return dynamic_modint(u);
}
friend std::ostream& operator<<(std::ostream& os, const dynamic_modint& m) {
return os << m.val;
}
friend std::istream& operator>>(std::istream& is, dynamic_modint& m) {
ll x;
is >> x;
m = dynamic_modint(x);
return is;
}
};
#endif /* MODINT__HPP_ */
#ifndef PRIME_AND_DIVISORS_HPP_
#define PRIME_AND_DIVISORS_HPP_
#include <array>
#include <algorithm>
#include <cassert>
#include <numeric>
#include <iostream>
using namespace std;
using ll = long long;
using ulll = __uint128_t;
using pll = array<ll,2>;
using pull = array<ull,2>;
using pii = array<int,2>;
/// @brief 試し割り法で正の整数Nを素因数分解する
/// @return list<array<ll,2>>{{素因数1,個数}, {素因数2,個数}, {素因数3,個数}...}
template<typename T> constexpr list<array<T,2>> trial_division(T N){
assert(N > 0);
if (N == 1){
return list<array<T,2>> {{1,0}};
}
list<array<T,2>> R;//戻り値用リスト
const T M = isqrt(static_cast<ull>(N));
for (T i = 2; i <= M; i++){
if (N % i == 0){
T divide_count = 0;
while (N % i == 0){
divide_count++;
N /= i;
}
R.append({i,divide_count});
}
}
if (N != 1){
R.append({N,1});
}
return R;
}
/// @brief 素因数分解リストを受け取って約数関数の値を求める
/// @return 約数のK乗和
template<typename T> constexpr T divisor_function(const list<array<T,2>>& vv, T K, const T MOD = -1){
if (vv[0][0] == 1){
return 1;
}
T R = 1;
if (K == 0){
for (auto x : vv){
R *= x[1]+1;
if (MOD > 0){
R %= MOD;
}
}
}
else{
for (auto x : vv){
ll r = powll(x[0],K);
R *= (powll(r,x[1]+1) - 1)/(r - 1);
if (MOD > 0){
R %= MOD;
}
}
}
return R;
}
/// @brief 素因数分解の結果pを受け取って、約数リストを生成する。
template<typename T> constexpr list<T> enumerate_divisor(const list<array<T,2>>& p){
list<T> d{1};
if (p[0][0] == 1){
return d;
}
for (auto &v : p){
T t = d.size();
T temp = 1;
for (T w = 0; w < v[1]; w++){
temp *= v[0];
for (T i = 0; i < t; i++){
d.append(d[i]*temp);
}
}
}
sort(vall(d));
return d;
}
/// @brief 線形篩
/// @attention コンストラクタに整数Nを渡すことでN以下の整数を扱うことができる。
struct LinearSieve{
list<int> p_list;
list<int> lpf;
//Nを渡すことで1以上N以下の整数を扱うことができる
LinearSieve(int N): lpf(N+1,-1){
lpf[1] = 1;
int p_list_size = 0;
for (int i = 2; i <= N; i++){
if (lpf[i] < 0){
p_list.append(i);
p_list_size++;
lpf[i] = i;
}
for (int j = 0; j < p_list_size && p_list[j] <= lpf[i] && p_list[j]*i <= N; j++){
lpf[p_list[j]*i] = p_list[j];
}
}
}
list<pii> factorize(int x){
if (x == 1){return {{1,0}};}
list<pii> r;
do{
if (r.empty() || lpf[x] != r.back()[0]){
r.append({lpf[x], 1});
}
else{
r.back()[1]++;
}
x /= lpf[x];
}while(x > 1);
return r;
}
list<list<pii>> factorize_all(int N){
list<list<pii>> r(N+1);
r[1].append({1,0});
for (int i = 2; i <= N; i++){
r[i] = factorize(i);
}
return r;
}
/// @brief N以下の整数に対するメビウス関数の値を列挙する。
list<int> enumerate_mobius(int N){
list<int> ret(N+1);
ret[1] = 1;
for (int i = 2; i <= N; i++){
if (lpf[i] == i){ret[i] = -1; continue;}
int temp = i/lpf[i];
if (lpf[i] == lpf[temp]){
ret[i] = 0;
}
else{
ret[i] = ret[lpf[i]]*ret[temp];
}
}
return ret;
}
};
constexpr ull __MillerRabin_small[3] = {2,7,61};
constexpr ull __MillerRabin_large[7] = {2,325,9375,28178,450775,9780504,1795265022};
struct Montgomery64 {
ull n, ni, r2;
constexpr Montgomery64(ull n) : n(n), ni(n), r2(-ulll(n) % n){
for (int i = 0; i < 5; ++i) ni *= 2ull - n * ni;
ni *= -1;
}
constexpr ull reduce(ulll x) const {
ull m = (ull)x * ni;
ull res = (x + ulll(m) * n) >> 64;
return res >= n ? res - n : res;
}
constexpr ull mul(ull x, ull y) const {
return reduce(ulll(x) * y);
}
constexpr ull pow_not_reduced(ull a, ull b)const{
ull res = reduce(r2);
a = reduce(ulll(a) * r2);
while (b) {
if (b & 1) res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
};
///@brief ミラーラビン素数判定法
template<typename T> constexpr bool MillerRabin(T N){
if (N <= 1) return false;
if (N == 2 || N == 3) return true;
if (N % 2 == 0) return false;
T d = N - 1;
T s = 0;
while (d % 2 == 0){
d >>= 1;
s++;
}
auto modpow_T = [&](T a,T b,T m){
T t = a%m;
T ans = (m == 1 ? 0 : 1);
while (b > 0){
if (b&1){
ans = (ans*t)%m;
}
b >>= 1;
t = (t*t)%m;
}
return ans;
};
auto check = [&](T a){
if (a >= N) a %= N;
if (a == 0) return true;
T x = modpow_T(a, d, N);
if (x == 1 || x == N-1) return true;
for (int r = 1; r < s; r++){
x = x*x%N;
if (x == N - 1) return true;
}
return false;
};
if (N < 4759123141){
for (auto a : __MillerRabin_small){
if (!check(static_cast<T>(a))) return false;
}
}
else if (N < 1000000000000000000){
for (auto a : __MillerRabin_large){
if (!check(static_cast<T>(a))) return false;
}
}
else{
for (auto a : __MillerRabin_large){
if (!check(static_cast<T>(a))) return false;
}
//50個の整数でテスト
for (T a = 638245987265732141; a < 638245987265732191; a++){
if (!check(a)) return false;
}
}
return true;
}
/// @brief ミラーラビン素数判定法のull範囲限定版
template<> constexpr bool MillerRabin(ull N){
if (N <= 1) return false;
if (N == 2 || N == 3) return true;
if (N % 2 == 0) return false;
ull d = N - 1;
int s = 0;
while (d % 2 == 0){
d >>= 1;
s++;
}
Montgomery64 mg(N);
auto check = [&](ull a){
if (a >= N) a %= N;
if (a == 0) return true;
ull x = mg.pow_not_reduced(a, d);
ull y = mg.reduce(x);
if (y == 1 || y == N-1) return true;
for (int r = 1; r < s; r++){
x = mg.mul(x, x);
if (mg.reduce(x) == N - 1) return true;
}
return false;
};
if (N < 4759123141ull){
for (auto a : __MillerRabin_small){
if (!check(a)) return false;
}
}
else{
for (auto a : __MillerRabin_large){
if (!check(a)) return false;
}
}
return true;
}
/// @brief ポラード・ロー法による素因数分解
template<typename T> constexpr list<array<T, 2>> Pollard_rho(T N){
assert(N > 0);
if (N == 1){return {{1,0}};}
list<T> res;
list<T> dq;
dq.append(N);
while (!dq.empty()){
T n = dq.back();
dq.pop();
bool next_loop = false;
while (!MillerRabin<T>(n)){
if ((n&1) == 0){
while ((n&1) == 0){res.append(2); n>>=1;}
if (n == 1){next_loop = true; break;}
continue;
}
T blocksize = sqrt(sqrt(sqrt(n)));
for (T c = 1; c <= n; c++){
T y = (0b1010110101101011110011ull^c^n)%n;
T r = 1;
T k = 0;
T k_mod_blocksize = 0;
bool next_loop_inner = false;
for (int _ = 0;;){
T q = 1;
T q_old = q;
T y_old = y;
T x = y;
while (k < r){
k++;
k_mod_blocksize++;
y = y*y%n+c; if (y >= n){ y -= n;}
q = q*(y >= x ? (y-x) : (x-y))%n;
if (k_mod_blocksize == blocksize){
k_mod_blocksize -= blocksize;
T g = gcd(q,n);
if (g > 1){
if (g != n){
dq.append(g);
dq.append(n/g);
next_loop = true; break;
}
else{
y = y_old;
q = q_old;
for (int i = 0; i < blocksize; i++){
y = y*y%n+c; if (y >= n){ y -= n;}
q = q*(y >= x ? (y-x) : (x-y))%n;
g = gcd(q,n);
if (g > 1){
if (g != n){
dq.append(g);
dq.append(n/g);
next_loop = true; break;
}
next_loop_inner = true; break;
}
}
if (next_loop || next_loop_inner) break;
}
}
q_old = q;
y_old = y;
}
}
if (next_loop || next_loop_inner) break;
q_old = gcd(q,n);
if (q_old > 1){
if (q_old != n){
dq.append(q_old);
dq.append(n/q_old);
next_loop = true; break;
}
next_loop_inner = true; break;
}
r <<= 1;
}
if (next_loop) break;
}
if (next_loop) break;
}
if (!next_loop) {
res.append(n);
}
}
sort(res.begin(), res.end());
list<array<T,2>> res2;
for (ull l = 0, r = 0, sz = res.size(); l < sz;){
while (r < sz && res[l] == res[r]){
r++;
}
res2.append({res[l], r-l});
l = r;
}
return res2;
}
/// @brief ポラード・ロー法による素因数分解のull範囲限定版
template<> constexpr list<pull> Pollard_rho(ull N){
assert(N > 0);
if (N == 1){return {{1,0}};}
list<ull> res;
list<ull> dq;
dq.append(N);
while (!dq.empty()){
ull n = dq.back();
dq.pop();
bool next_loop = false;
while (!MillerRabin<ull>(n)){
if ((n&1) == 0){
while ((n&1) == 0){res.append(2); n>>=1;}
if (n == 1){next_loop = true; break;}
continue;
}
Montgomery64 mg(n);
int blocksize = max<int>(1, pow(n, 0.125));
for (ull c = 1; c <= n; c++){
ull reduced_c = mg.reduce(c*(ulll)mg.r2);
ull y = (0b1010110101101011110011ull^c^n)%n; y = mg.reduce(y*(ulll)mg.r2);
ull r = 1;
ull k = 0;
int k_mod_blocksize = 0;
bool next_loop_inner = false;
for (int _ = 0; _ < 63; _++){
ull q = mg.reduce(mg.r2);
ull q_old = q;
ull y_old = y;
ull x = y;
while (k < r){
k++;
k_mod_blocksize++;
y = mg.reduce(y*(ulll)y)+reduced_c; if (y >= n){ y -= n;}
q = mg.reduce(q*(y >= x ? (ulll)(y-x) : (ulll)(x-y)));
if (k_mod_blocksize == blocksize){
k_mod_blocksize -= blocksize;
ull g = gcd(mg.reduce(q),n);
if (g > 1){
if (g != n){
dq.append(g);
dq.append(n/g);
next_loop = true; break;
}
else{
y = y_old;
q = q_old;
for (int i = 0; i < blocksize; i++){
y = mg.reduce(y*(ulll)y)+reduced_c; if (y >= n){ y -= n;}
q = mg.reduce(q*(y >= x ? (ulll)(y-x) : (ulll)(x-y)));
g = gcd(mg.reduce(q),n);
if (g > 1){
if (g != n){
dq.append(g);
dq.append(n/g);
next_loop = true; break;
}
next_loop_inner = true; break;
}
}
if (next_loop || next_loop_inner) break;
}
}
q_old = q;
y_old = y;
}
}
if (next_loop || next_loop_inner) break;
q_old = gcd(mg.reduce(q),n);
if (q_old > 1){
if (q_old != n){
dq.append(q_old);
dq.append(n/q_old);
next_loop = true; break;
}
next_loop_inner = true; break;
}
r <<= 1;
}
if (next_loop) break;
}
if (next_loop) break;
}
if (!next_loop) {
res.append(n);
}
}
sort(res.begin(), res.end());
list<pull> res2;
for (int l = 0, r = 0, sz = res.size(); l < sz;){
while (r < sz && res[l] == res[r]){
r++;
}
res2.append({res[l], static_cast<ull>(r-l)});
l = r;
}
return res2;
}
/// @brief 素因数分解を行う。`N`の大きさによって、試し割り法とポラード・ロー法を使い分けてくれる。
template<typename T> constexpr list<array<T, 2>> factorize(T N){
if (N < 640000){
return trial_division<T>(N);
}
if (N < 1000000000000000000){
return Pollard_rho<T>(N);
}
return Pollard_rho<T>(N);
}
template<> constexpr list<pull> factorize(ull N){
if (N < 640000ull){
return trial_division<ull>(N);
}
return Pollard_rho<ull>(N);
}
template<> constexpr list<pll> factorize(ll N){
auto res = factorize<ull>(N);
list<pll> res2(res.size());
for (int i = 0, sz = res.size(); i < sz; i++){
res2[i][0] = res[i][0];
res2[i][1] = res[i][1];
}
return res2;
}
template<> constexpr list<pii> factorize(int N){
auto res = factorize<ull>(N);
list<pii> res2(res.size());
for (int i = 0, sz = res.size(); i < sz; i++){
res2[i][0] = res[i][0];
res2[i][1] = res[i][1];
}
return res2;
}
struct Xorshift64{
ull state;
constexpr Xorshift64(ull seed = 881726454633252252ull) : state(seed) {}
constexpr ull next() {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
return state;
}
};
/// @brief mod Pにおける原始根を1つ探す。Pはull範囲内の素数でなければならない。
constexpr ull primitive_root(ull P){
assert(MillerRabin<ull>(P));
if (P == 2){
return 1;
}
Montgomery64 mg(P);
Xorshift64 rng(0x1234567E89ABCDEF);
auto factorized = factorize<ull>(P-1);
while (true) {
ull r = rng.next()%P;
if (r == 0){continue;}
bool ok = true;
for (auto& q : factorized){
if (mg.reduce(mg.pow_not_reduced(r, (P-1)/q[0])) == 1){
ok = false;
break;
}
}
if (ok) return r;
}
}
#endif /* PRIME_AND_DIVISORS_HPP_ */
#include <map>
#ifndef FLOOR_OF_LINEAR_HPP_
#define FLOOR_OF_LINEAR_HPP_
#include <cassert>
template<typename T> constexpr T internal_floor_sum(T A, T B, T C){
if (C < 0){return 0;}
if (A > B){swap(A,B);}
if (B%A == 0){
return (1+floor2<T>(C,A))*(1+floor2<T>(C,B)) - (B/A)*floor2<T>(C,B)*(floor2<T>(C,B)+1)/2;
}
T k = floor2<T>(C-B*floor2<T>(C,B),A);
return (1+k)*(1+floor2<T>(C,B)) + floor2<T>(B,A)*floor2<T>(C,B)*(floor2<T>(C,B)+1)/2 + internal_floor_sum<T>(A, B%A, C-A*(floor2<T>(B,A)*floor2<T>(C,B)+k+1));
}
/// @brief `\sum_{i=0}^{N} \lfloor\frac{Ci+D}{B}\rfloor`を求める。
template<typename T> constexpr T floor_sum(T N, T B, T C, T D){
if (N < 0){
return 0;
}
if (B < 0){//Bを負にする。
B *= -1;
C *= -1;
D *= -1;
}
if (C > 0){//Cを負にするが、Cを-Cに置き換えてC>0として扱う。
D += N*C;
}
else{
C *= -1;
}
if (C == 0){
return (N+1)*floor2<T>(D,B);
}
T k = floor2<T>(D-C*N,B);
return (N+1)*k + internal_floor_sum<T>(B,C,D-B*(k+1));
}
//T generalized_floor_sum_1_1(T N, T B, T C, T D){
// return 0;
//}
//T generalized_floor_sum_0_2(T N, T B, T C, T D){
// return 0;
//}
template<typename T> constexpr T internal_floor_max(T A, T B, T C, T D, T E, T F){
if (D < 0){return -1000000000000000000;}
if (C <= 0){return -1000000000000000000;}
if (E > 0){
if (B > C){swap(A,E);swap(B,C);}
T M = floor2<T>(D-C*floor2<T>(D, C), B);
T tempans = max<T>(A*M+E*floor2<T>(D, C), A*floor2<T>(D, B)) + F;
return max<T>(tempans, A*(1+M)+internal_floor_max<T>(A, B, C%B, D-B*(1+M+floor2<T>(C, B)*floor2<T>(D, C)), E-A*floor2<T>(C, B), F+A*floor2<T>(C, B)*floor2<T>(D, C)));
}
else return A*floor2<T>(D, B) + F;
}
/// @brief `0<=x<=N`の下で、`A*floor2(C*x+D, B)+E*x+F`の最大値を求める。もし何かがおかしいなら`-10^18`が返される。
/// @param N
/// @param A
/// @param B
/// @param C
/// @param D
/// @param E
/// @param F
/// @return `max`
template<typename T> constexpr T floor_max(T N, T A, T B, T C, T D, T E, T F){
if (N < 0){
return -1000000000000000000;
}
assert(B != 0);
//マイナスを処理
if (B < 0){
B *= -1;
C *= -1;
D *= -1;
}
if (A < 0){
A *= -1;
C *= -1;
D *= -1;
D += B-1;
}
//自明なケース
if (C == 0 or A == 0){
return A*floor2<T>(D, B) + F + max<T>(0, E*N);
}
if (E == 0){
return A*floor2<T>(max<T>(0, C*N)+D, B) + F;
}
//Cの係数を調整
if (C > 0){
F += E*N;
E *= -1;
D += C*N;
}
else{
//`A*floor2(D-C*x, B)+E*x+F`, `A,B,C>0`にする
C *= -1;
}
//自明なケースを処理
if (E < 0){
return A*floor2<T>(D, B) + F;
}
T x_offset = floor2<T>(D-C*N, B)+1;
D -= B*x_offset;
return A*x_offset + max<T>(internal_floor_max<T>(A,B,C,D,E,F), -A+E*N+F);
}
#endif /* FLOOR_OF_LINEAR_HPP_ */
ll solve(){
// ll MAX = 5000;
// map<list<ll>,list<ll>> temp;
// for (ll N = 2; N <= MAX; N++){
// for (ll M = 1; M <= MAX; M++){
// list<ll> key;
// key = {floor_sum<ll>(N-1, M, MAX, 0), floor_sum<ll>(N-1, M, MAX, MAX)};
// temp[key] += N;
// }
// }
// map<list<ll>, ll> temp2;
// ll temp4 = 0;
// for (auto [k,v] : temp){
// v.sort();
// v.erase(unique(vall(v)), v.end());
// temp2[k] = len(v);
// temp4 = max(temp4, len(v));
// if (len(v) >= 2){
// print(k);
// print(v);
// }
// }
// print(temp4);
auto ask = [&](ll A, ll B){
// return floor_sum(N-1, M, A, B);
print("?",A,B);
out.flush();
ll res;
in >> res;
return res;
};
ll X = ask(1, 1000000);
ll Y = ask(1000000, 1000000);
if (X == Y){
return 1;
}
ll Z = ask(1000000, 0);
ll N_temp = (2*Z)/(Y-Z);
for (ll n = max(1ll, N_temp - 1000); n <= min(1000000ll, N_temp+1000); n++){
ll ok = 1;
ll ng = 1000001;
if (1000000*n*(n-1)/2 < Z){continue;}
while (ng-ok > 1){
ll mid = (ok+ng)/2;
if (floor_sum(n-1, mid, 1000000ll, 0ll) >= Z){
ok = mid;
}
else{
ng = mid;
}
}
if (floor_sum(n-1, ok, 1000000ll, 0ll) == Z){
ll ok2 = 1;
ll ng2 = 1000001;
while (ng2-ok2 > 1){
ll mid = (ok2+ng2)/2;
if (floor_sum(n-1, mid, 1000000ll, 0ll) >= Z+1){
ok2 = mid;
}
else{
ng2 = mid;
}
}
ll l = ok2;
ll r = ok;
if (floor_sum(n-1, l, 1000000ll, 1000000ll) < Y){
continue;
}
while (r-l > 2){
ll mid = (l+r)/2;
if (floor_sum(n-1, l, 1000000ll, 1000000ll) >= Y){
l = mid;
}
else{
r = mid;
}
}
for (ll i = l; i <= r; i++){
if (floor_sum(n-1, i, 1000000ll, 1000000ll) == Y){
return n;
}
}
}
}
return -1;
}
#ifndef RANDINT__HPP_
#define RANDINT__HPP_
#include <random>
#include <cassert>
using ll = long long;
using ull = unsigned long long;
using namespace std;
/// @brief 符号付き64bit整数の範囲内の乱数を生成する。
struct randint{
mt19937_64 mt;
uniform_int_distribution<ull> ui;
randint(ll seed = 9223372036854775807ll){
if (seed == 9223372036854775807ll){
random_device rd;
mt = mt19937_64(rd());
}
else{
mt = mt19937_64(seed);
}
ui = uniform_int_distribution<ull>(0, 18446744073709551615ull);
};
/// @brief `L`以上`R`未満の乱数を生成する。
/// @param L
/// @param R
ll gen(ll L = -9223372036854775807ll, ll R = 9223372036854775807ll){
assert(L<R);
ull M = R-L;
return ui(mt)%M+L;
}
};
#endif /* RANDINT__HPP_ */
randint r;
int main(){
// ios::sync_with_stdio(false);
// std::cin.tie(nullptr);
ll T = 1;
in >> T;
while (T--){
// ll N = r.gen(1, 1000001);
// ll M = r.gen(1, 1000001);
// ll N = 595, M = 666861;
// ll res = solve(N,M);
// if (res != N){
// print(N, res);
// out.flush();
// }
print("!", solve());
}
}