結果
| 問題 | No.3772 Discrete Addition |
| コンテスト | |
| ユーザー |
 kaichou243
|
| 提出日時 | 2026-10-15 02:20:06 |
| 言語 | C++17 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 2,748 ms / 8,000 ms |
| + 646µs | |
| コード長 | 28,525 bytes |
| 記録 | |
| コンパイル時間 | 3,655 ms |
| コンパイル使用メモリ | 390,912 KB |
| 実行使用メモリ | 10,060 KB |
| 最終ジャッジ日時 | 2026-10-16 20:58:56 |
| 合計ジャッジ時間 | 12,797 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge4_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 12 |
ソースコード
#include<bits/stdc++.h>
#include <immintrin.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define all(v) (v).begin(), (v).end()
using namespace std;
using ll=long long;
using i128=__int128;
using P = pair<ll,ll>;
const long double PI=acos(-1);
const ll INF=1e18;
const int inf=1e9;
struct Edge {
ll to;
ll cost;
};
using Graph=vector<vector<Edge>>;
template <typename T>
bool chmax(T &a,const T& b){
if (a<b){
a=b;
return true;
}
return false;
}
template <typename T>
bool chmin(T &a,const T& b){
if (a>b){
a=b;
return true;
}
return false;
}
template<int MOD> struct Fp{
ll val;
constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
if (val < 0) val += MOD;
}
static constexpr int getmod() { return MOD; }
constexpr Fp operator - () const noexcept {
return val ? MOD - val : 0;
}
constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
constexpr Fp& operator += (const Fp& r) noexcept {
val += r.val;
if (val >= MOD) val -= MOD;
return *this;
}
constexpr Fp& operator -= (const Fp& r) noexcept {
val -= r.val;
if (val < 0) val += MOD;
return *this;
}
constexpr Fp& operator *= (const Fp& r) noexcept {
val = val * r.val % MOD;
return *this;
}
constexpr Fp& operator /= (const Fp& r) noexcept {
ll a = r.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);
}
val = val * u % MOD;
if (val < 0) val += MOD;
return *this;
}
constexpr bool operator == (const Fp& r) const noexcept {
return this->val == r.val;
}
constexpr bool operator != (const Fp& r) const noexcept {
return this->val != r.val;
}
constexpr bool operator < (const Fp& r) const noexcept {
return this->val < r.val;
}
friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {
is >> x.val;
x.val %= MOD;
if (x.val < 0) x.val += MOD;
return is;
}
friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {
return os << x.val;
}
friend constexpr Fp<MOD> modpow(const Fp<MOD>& a, long long n) noexcept {
Fp<MOD> res=1,r=a;
while(n){
if(n&1) res*=r;
r*=r;
n>>=1;
}
return res;
}
friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {
long long a = r.val, b = MOD, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b, swap(a, b);
u -= t * v, swap(u, v);
}
return Fp<MOD>(u);
}
ll get(){
return val;
}
explicit operator bool()const{
return val;
}
};
template< uint32_t mod, bool fast = false >
struct MontgomeryModInt {
using mint = MontgomeryModInt;
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
static constexpr u32 get_r() {
u32 ret = mod;
for(i32 i = 0; i < 4; i++) ret *= 2 - mod * ret;
return ret;
}
static constexpr u32 r = get_r();
static constexpr u32 n2 = -u64(mod) % mod;
static_assert(r * mod == 1, "invalid, r * mod != 1");
static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");
static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");
u32 a;
MontgomeryModInt() : a{} {}
MontgomeryModInt(const i64 &x)
: a(reduce(u64(fast ? x : (x % mod + mod)) * n2)) {}
static constexpr u32 reduce(const u64 &b) {
return u32(b >> 32) + mod - u32((u64(u32(b) * r) * mod) >> 32);
}
constexpr mint& operator+=(const mint &p) {
if(i32(a += p.a - 2 * mod) < 0) a += 2 * mod;
return *this;
}
constexpr mint& operator-=(const mint &p) {
if(i32(a -= p.a) < 0) a += 2 * mod;
return *this;
}
constexpr mint& operator*=(const mint &p) {
a = reduce(u64(a) * p.a);
return *this;
}
constexpr mint& operator/=(const mint &p) {
*this *= modinv(p);
return *this;
}
constexpr mint operator-() const { return mint() - *this; }
constexpr mint operator+(const mint &p) const { return mint(*this) += p; }
constexpr mint operator-(const mint &p) const { return mint(*this) -= p; }
constexpr mint operator*(const mint &p) const { return mint(*this) *= p; }
constexpr mint operator/(const mint &p) const { return mint(*this) /= p; }
constexpr bool operator==(const mint &p) const { return (a >= mod ? a - mod : a) == (p.a >= mod ? p.a - mod : p.a); }
constexpr bool operator!=(const mint &p) const { return (a >= mod ? a - mod : a) != (p.a >= mod ? p.a - mod : p.a); }
u32 get() const {
u32 ret = reduce(a);
return ret >= mod ? ret - mod : ret;
}
friend constexpr MontgomeryModInt<mod> modpow(const MontgomeryModInt<mod> &x,u64 n) noexcept {
MontgomeryModInt<mod> ret(1), mul(x);
while(n > 0) {
if(n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend constexpr MontgomeryModInt<mod> modinv(const MontgomeryModInt<mod> &r) noexcept {
u64 a = r.get(), b = mod, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b, swap(a, b);
u -= t * v, swap(u, v);
}
return MontgomeryModInt<mod>(u);
}
friend ostream &operator<<(ostream &os, const mint &p) {
return os << p.get();
}
friend istream &operator>>(istream &is, mint &a) {
i64 t;
is >> t;
a = mint(t);
return is;
}
static constexpr u32 getmod() { return mod; }
};
ll mod(ll a, ll mod) {
return (a%mod+mod)%mod;
}
ll modpow(ll a,ll n,ll mod){
ll res=1;
a%=mod;
while (n>0){
if (n & 1) res*=a;
a *= a;
a%=mod;
n >>= 1;
res%=mod;
}
return res;
}
vector<P> prime_factorize(ll N) {
vector<P> res;
for (ll a = 2; a * a <= N; ++a) {
if (N % a != 0) continue;
ll ex = 0;
while(N % a == 0){
++ex;
N /= a;
}
res.push_back({a, ex});
}
if (N != 1) res.push_back({N, 1});
return res;
}
ll modinv(ll a, ll mod) {
ll b = mod, u = 1, v = 0;
while (b) {
ll t = a/b;
a -= t * b, swap(a, b);
u -= t * v, swap(u, v);
}
u %= mod;
if (u < 0) u += mod;
return u;
}
ll extGcd(ll a, ll b, ll &p, ll &q) {
if (b == 0) { p = 1; q = 0; return a; }
ll d = extGcd(b, a%b, q, p);
q -= a/b * p;
return d;
}
P ChineseRem(const vector<ll> &b, const vector<ll> &m) {
ll r = 0, M = 1;
for (int i = 0; i < (int)b.size(); ++i) {
ll p, q;
ll d = extGcd(M, m[i], p, q);
if ((b[i] - r) % d != 0) return make_pair(0, -1);
ll tmp = (b[i] - r) / d * p % (m[i]/d);
r += M * tmp;
M *= m[i]/d;
}
return make_pair(mod(r, M), M);
}
#include <unistd.h>
namespace fastio {
#define FASTIO
struct has_write_impl {
template <class T>
static auto check(T &&x) -> decltype(x.write(), std::true_type{});
template <class T>
static auto check(...) -> std::false_type;
};
template <class T>
class has_write : public decltype(has_write_impl::check<T>(std::declval<T>())) {
};
struct has_read_impl {
template <class T>
static auto check(T &&x) -> decltype(x.read(), std::true_type{});
template <class T>
static auto check(...) -> std::false_type;
};
template <class T>
class has_read : public decltype(has_read_impl::check<T>(std::declval<T>())) {};
struct Scanner {
FILE *fp;
char line[(1 << 15) + 1];
size_t st = 0, ed = 0;
void reread() {
memmove(line, line + st, ed - st);
ed -= st;
st = 0;
ed += fread(line + ed, 1, (1 << 15) - ed, fp);
line[ed] = '\0';
}
bool succ() {
while (true) {
if (st == ed) {
reread();
if (st == ed) return false;
}
while (st != ed && isspace(line[st])) st++;
if (st != ed) break;
}
if (ed - st <= 50) {
bool sep = false;
for (size_t i = st; i < ed; i++) {
if (isspace(line[i])) {
sep = true;
break;
}
}
if (!sep) reread();
}
return true;
}
template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
bool read_single(T &ref) {
if (!succ()) return false;
while (true) {
size_t sz = 0;
while (st + sz < ed && !isspace(line[st + sz])) sz++;
ref.append(line + st, sz);
st += sz;
if (!sz || st != ed) break;
reread();
}
return true;
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
bool read_single(T &ref) {
if (!succ()) return false;
bool neg = false;
if (line[st] == '-') {
neg = true;
st++;
}
ref = T(0);
while (isdigit(line[st])) { ref = 10 * ref + (line[st++] & 0xf); }
if (neg) ref = -ref;
return true;
}
template <typename T,
typename enable_if<has_read<T>::value>::type * = nullptr>
inline bool read_single(T &x) {
x.read();
return true;
}
bool read_single(double &ref) {
string s;
if (!read_single(s)) return false;
ref = std::stod(s);
return true;
}
bool read_single(char &ref) {
string s;
if (!read_single(s) || s.size() != 1) return false;
ref = s[0];
return true;
}
template <class T>
bool read_single(vector<T> &ref) {
for (auto &d: ref) {
if (!read_single(d)) return false;
}
return true;
}
template <class T, class U>
bool read_single(pair<T, U> &p) {
return (read_single(p.first) && read_single(p.second));
}
template <size_t N = 0, typename T>
void read_single_tuple(T &t) {
if constexpr (N < std::tuple_size<T>::value) {
auto &x = std::get<N>(t);
read_single(x);
read_single_tuple<N + 1>(t);
}
}
template <class... T>
bool read_single(tuple<T...> &tpl) {
read_single_tuple(tpl);
return true;
}
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
bool f = read_single(h);
assert(f);
read(t...);
}
Scanner(FILE *fp) : fp(fp) {}
};
struct Printer {
Printer(FILE *_fp) : fp(_fp) {}
~Printer() { flush(); }
static constexpr size_t SIZE = 1 << 15;
FILE *fp;
char line[SIZE], small[50];
size_t pos = 0;
void flush() {
fwrite(line, 1, pos, fp);
pos = 0;
}
void write(const char val) {
if (pos == SIZE) flush();
line[pos++] = val;
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
void write(T val) {
if (pos > (1 << 15) - 50) flush();
if (val == 0) {
write('0');
return;
}
if (val < 0) {
write('-');
val = -val; // todo min
}
size_t len = 0;
while (val) {
small[len++] = char(0x30 | (val % 10));
val /= 10;
}
for (size_t i = 0; i < len; i++) { line[pos + i] = small[len - 1 - i]; }
pos += len;
}
void write(const string s) {
for (char c: s) write(c);
}
void write(const char *s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) write(s[i]);
}
void write(const double x) {
ostringstream oss;
oss << fixed << setprecision(15) << x;
string s = oss.str();
write(s);
}
void write(const long double x) {
ostringstream oss;
oss << fixed << setprecision(15) << x;
string s = oss.str();
write(s);
}
template <typename T,
typename enable_if<has_write<T>::value>::type * = nullptr>
inline void write(T x) {
x.write();
}
template <class T>
void write(const vector<T> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write(' ');
write(val[i]);
}
}
template <class T, class U>
void write(const pair<T, U> val) {
write(val.first);
write(' ');
write(val.second);
}
template <size_t N = 0, typename T>
void write_tuple(const T t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) { write(' '); }
const auto x = std::get<N>(t);
write(x);
write_tuple<N + 1>(t);
}
}
template <class... T>
bool write(tuple<T...> tpl) {
write_tuple(tpl);
return true;
}
template <class T, size_t S>
void write(const array<T, S> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write(' ');
write(val[i]);
}
}
void write(i128 val) {
string s;
bool negative = 0;
if (val < 0) {
negative = 1;
val = -val;
}
while (val) {
s += '0' + int(val % 10);
val /= 10;
}
if (negative) s += "-";
reverse(all(s));
if (sz(s) == 0) s = "0";
write(s);
}
};
Scanner scanner = Scanner(stdin);
Printer printer = Printer(stdout);
void flush() { printer.flush(); }
void print() { printer.write('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
printer.write(head);
if (sizeof...(Tail)) printer.write(' ');
print(forward<Tail>(tail)...);
}
void print2() {}
template <class Head, class... Tail>
void print2(Head &&head, Tail &&... tail){
printer.write(head);
if(sizeof...(Tail)) printer.write(' ');
print2(forward<Tail>(tail)...);
}
void read() {}
template <class Head, class... Tail>
void read(Head &head, Tail &... tail) {
scanner.read(head);
read(tail...);
}
} // namespace fastio
using fastio::print;
using fastio::flush;
using fastio::read;
using fastio::printer;
using fastio::print2;
constexpr bool is_prime(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = modpow(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template< typename T >
struct Combination {
vector< T > _fact, _rfact, _inv;
Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {
_fact[0] = _rfact[sz] = _inv[0] = 1;
for(int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;
_rfact[sz] /= _fact[sz];
for(int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);
for(int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];
}
inline T fact(int k) const { return _fact[k]; }
inline T rfact(int k) const { return _rfact[k]; }
inline T inv(int k) const { return _inv[k]; }
T P(int n, int r) const {
if(r < 0 || n < r) return 0;
return fact(n) * rfact(n - r);
}
T C(int p, int q) const {
if(q < 0 || p < q) return 0;
return fact(p) * rfact(q) * rfact(p - q);
}
T H(int n, int r) const {
if(n < 0 || r < 0) return (0);
return r == 0 ? 1 : C(n + r - 1, r);
}
};
ll rand_int(ll l, ll r) { //[l, r]
#ifdef LOCAL
static mt19937_64 gen;
#else
static random_device rd;
static mt19937_64 gen(rd());
#endif
return uniform_int_distribution<ll>(l, r)(gen);
}
template<class T,T (*op)(T,T),T (*e)()> struct SegmentTree{
int n;
vector<T> dat;
SegmentTree(int N){
n=1;
while(n<N)n*=2;
dat.assign(2*n,e());
}
void add(int k,T x){
k+=n;
dat[k]+=x;
while(k){
k>>=1;
dat[k]=op(dat[k*2],dat[k*2+1]);
}
}
void apply(int k,T x){
k+=n;
dat[k]=op(dat[k],x);
while(k){
k>>=1;
dat[k]=op(dat[k*2],dat[k*2+1]);
}
}
void set(int k,T x){
k+=n;
dat[k]=x;
while(k){
k>>=1;
dat[k]=op(dat[k*2],dat[k*2+1]);
}
}
T query(int l,int r){
T prodl=e(),prodr=e();
l+=n;
r+=n;
while(l<r){
if(l&1) prodl=op(prodl,dat[l++]);
if(r&1) prodr=op(dat[--r],prodr);
l>>=1;
r>>=1;
}
return op(prodl,prodr);
}
};
template<class S,S (*op)(S,S),S (*e)(),class F,S (*mapping)(F,S),F (*composition)(F,F),F (*id)()>
struct LazySegTree{
private:
int _n,size=1,idx=0;
vector<S>seq;
vector<F>lazy;
void update(int k){seq[k]=op(seq[2*k],seq[2*k+1]);}
void all_apply(int k,F f){
seq[k]=mapping(f,seq[k]);
if(k<size)lazy[k]=composition(f,lazy[k]);
}
void eval(int k){
all_apply(2*k,lazy[k]);
all_apply(2*k+1,lazy[k]);
lazy[k]=id();
}
public:
LazySegTree(int n):LazySegTree(vector<S>(n,e())){}
LazySegTree(const vector<S>&v):_n(int(v.size())){
while(size<_n)size<<=1,idx++;
seq=vector<S>(2*size,e());
lazy=vector<F>(2*size,id());
for(int i=0;i<_n;i++)seq[size+i]=v[i];
for(int i=size-1;i>=1;i--)update(i);
}
void set(int p,S x){
p+=size;
for(int i=idx;i>=1;i--)eval(p>>i);
seq[p]=x;
for(int i=1;i<=idx;i++)update(p>>i);
}
void add(int p,S x){
p+=size;
for(int i=idx;i>=1;i--)eval(p>>i);
seq[p]+=x;
for(int i=1;i<=idx;i++)update(p>>i);
}
S operator[](int p){
p+=size;
for(int i=idx;i>=1;i--)eval(p>>i);
return seq[p];
}
S query(int l,int r){
if(l==r)return e();
S sml=e(),smr=e();
l+=size,r+=size;
for(int i=idx;i>=1;i--){
if(((l>>i)<<i)!=l)eval(l>>i);
if(((r>>i)<<i)!=r)eval(r>>i);
}
while(l<r){
if(l&1)sml=op(sml,seq[l++]);
if(r&1)smr=op(seq[--r],smr);
l>>=1,r>>=1;
}
return op(sml,smr);
}
S all_query()const{return seq[1];}
void apply(int p,F f){
p+=size;
for(int i=idx;i>=1;i--)eval(p>>i);
seq[p]=mapping(f,seq[p]);
for(int i=1;i<=idx;i++)update(p>>i);
}
void apply(int l,int r,F f){
if(l==r)return ;
l+=size;
r+=size;
for(int i=idx;i>=1;i--){
if(((l>>i)<<i)!=l)eval(l>>i);
if(((r>>i)<<i)!=r)eval((r-1)>>i);
}
int l2=l,r2=r;
while(l<r){
if(l&1)all_apply(l++,f);
if(r&1)all_apply(--r,f);
l>>=1;
r>>=1;
}
l=l2,r=r2;
for(int i=1;i<=idx;i++){
if(((l>>i)<<i)!=l)update(l>>i);
if(((r>>i)<<i)!=r)update((r-1)>>i);
}
}
};
template< typename flow_t >
struct MFGraph{
static_assert(is_integral< flow_t >::value, "template parameter flow_t must be integral type");
const flow_t INF;
struct edge {
int to;
flow_t cap;
int rev;
bool isrev;
int idx;
};
vector< vector< edge > > graph;
vector< int > min_cost, iter;
flow_t max_cap;
int SZ;
explicit MFGraph(int V) : INF(numeric_limits< flow_t >::max()), graph(V), max_cap(0), SZ(V) {}
void add_edge(int from, int to, flow_t cap, int idx = -1) {
max_cap = max(max_cap, cap);
graph[from].emplace_back((edge) {to, cap, (int) graph[to].size(), false, idx});
graph[to].emplace_back((edge) {from, 0, (int) graph[from].size() - 1, true, idx});
}
bool build_augment_path(int s, int t, const flow_t &base) {
min_cost.assign(graph.size(), -1);
queue< int > que;
min_cost[s] = 0;
que.push(s);
while(!que.empty() && min_cost[t] == -1) {
int p = que.front();
que.pop();
for(auto &e : graph[p]) {
if(e.cap >= base && min_cost[e.to] == -1) {
min_cost[e.to] = min_cost[p] + 1;
que.push(e.to);
}
}
}
return min_cost[t] != -1;
}
flow_t find_augment_path(int idx, const int t, flow_t base, flow_t flow) {
if(idx == t) return flow;
flow_t sum = 0;
for(int &i = iter[idx]; i < (int)graph[idx].size(); i++) {
edge &e = graph[idx][i];
if(e.cap >= base && min_cost[idx] < min_cost[e.to]) {
flow_t d = find_augment_path(e.to, t, base, min(flow - sum, e.cap));
if(d > 0) {
e.cap -= d;
graph[e.to][e.rev].cap += d;
sum += d;
if(flow - sum < base) break;
}
}
}
return sum;
}
flow_t max_flow(int s, int t) {
if(max_cap == flow_t(0)) return flow_t(0);
flow_t flow = 0;
for(int i = 63 - __builtin_clzll(max_cap); i >= 0; i--) {
flow_t now = flow_t(1) << i;
while(build_augment_path(s, t, now)) {
iter.assign(graph.size(), 0);
flow += find_augment_path(s, t, now, INF);
}
}
return flow;
}
//after max_flow(s,t)
vector<bool> min_cut(int s) {
vector<bool> visited(SZ);
queue<int> que;
que.push(s);
while (!que.empty()) {
int p = que.front();
que.pop();
visited[p] = true;
for (auto e : graph[p]) {
if (e.cap && !visited[e.to]) {
visited[e.to] = true;
que.push(e.to);
}
}
}
return visited;
}
void output() {
for(int i = 0; i < graph.size(); i++) {
for(auto &e : graph[i]) {
if(e.isrev) continue;
auto &rev_e = graph[e.to][e.rev];
cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
}
}
}
};
template< typename flow_t, typename cost_t >
struct MCFGraph{
struct edge {
int to;
flow_t cap;
cost_t cost;
int rev;
bool isrev;
};
vector< vector< edge > > graph;
vector< cost_t > potential, min_cost;
vector< int > prevv, preve;
const cost_t INF;
MCFGraph(int V) : graph(V), INF(numeric_limits< cost_t >::max()) {}
void add_edge(int from, int to, flow_t cap, cost_t cost) {
graph[from].emplace_back((edge) {to, cap, cost, (int) graph[to].size(), false});
graph[to].emplace_back((edge) {from, 0, -cost, (int) graph[from].size() - 1, true});
}
cost_t min_cost_flow(int s, int t, flow_t f) {
int V = (int) graph.size();
cost_t ret = 0;
using Pi = pair< cost_t, int >;
priority_queue< Pi, vector< Pi >, greater< Pi > > que;
potential.assign(V, 0);
preve.assign(V, -1);
prevv.assign(V, -1);
while(f > 0) {
min_cost.assign(V, INF);
que.emplace(0, s);
min_cost[s] = 0;
while(!que.empty()) {
Pi p = que.top();
que.pop();
if(min_cost[p.second] < p.first) continue;
for(int i = 0; i < (int)graph[p.second].size(); i++) {
edge &e = graph[p.second][i];
cost_t nextCost = min_cost[p.second] + e.cost + potential[p.second] - potential[e.to];
if(e.cap > 0 && min_cost[e.to] > nextCost) {
min_cost[e.to] = nextCost;
prevv[e.to] = p.second, preve[e.to] = i;
que.emplace(min_cost[e.to], e.to);
}
}
}
if(min_cost[t] == INF) return -1;
for(int v = 0; v < V; v++) potential[v] += min_cost[v];
flow_t addflow = f;
for(int v = t; v != s; v = prevv[v]) {
addflow = min(addflow, graph[prevv[v]][preve[v]].cap);
}
f -= addflow;
ret += addflow * potential[t];
for(int v = t; v != s; v = prevv[v]) {
edge &e = graph[prevv[v]][preve[v]];
e.cap -= addflow;
graph[v][e.rev].cap += addflow;
}
}
return ret;
}
void output() {
for(int i = 0; i < graph.size(); i++) {
for(auto &e : graph[i]) {
if(e.isrev) continue;
auto &rev_e = graph[e.to][e.rev];
cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << rev_e.cap + e.cap << ")" << endl;
}
}
}
};
struct UnionFind{
int n;
vector<int> data;
vector<int> edge_num;
UnionFind(int N) : n(N) , data(N,-1) , edge_num(N,0){}
int root(int x){ // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
return data[x]<0?x:data[x]=root(data[x]);
}
void unite(int x, int y) {
x=root(x);
y=root(y);
if(x!=y){
if (data[x]>data[y]) swap(x, y);
data[x]+=data[y];
data[y]=x;
}
if(x!=y){
edge_num[x]+=edge_num[y];
edge_num[y]=0;
}
edge_num[x]+=1;
}
bool same(int x, int y){ // 2つのデータx, yが属する木が同じならtrueを返す
return root(x)==root(y);
}
int size(int x){
return -data[root(x)];
}
int edge(int x){
return edge_num[root(x)];
}
vector<int> get_roots(){
vector<int> res;
for(int i=0;i<n;i++){
if(data[i]<0) res.push_back(i);
}
return res;
}
};
vector<ll> enum_divisors(ll N){
vector<ll> res;
for (ll i = 1; i * i <= N; ++i){
if (N % i == 0){
res.push_back(i);
// 重複しないならば i の相方である N/i も push
if (N/i != i) res.push_back(N/i);
}
}
// 小さい順に並び替える
sort(res.begin(), res.end());
return res;
}
using mint=MontgomeryModInt<998244353>;
#define in(...) read(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define outln(...) print(__VA_ARGS__)
#define out(...) print2(__VA_ARGS__)
#define outspace(...) print2(__VA_ARGS__),printer.write(' ')
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define endl '\n'
using i128=__int128_t;
struct LowerHull{
struct Point{ ll x; i128 y; };
vector<Point> h;
void add(ll x,i128 y){
Point p{x,y};
if(!h.empty()&&h.back().x==x) return;
while (h.size() >= 2) {
auto a=h[h.size()-2],b=h.back();
if((i128)(b.x-a.x)*(y-a.y)>(b.y-a.y)*(x-a.x)) break;
h.pop_back();
}
h.push_back(p);
}
//min(y + k*x)
i128 query(i128 k) const {
auto f=[&](int i){
return h[i].y+k*h[i].x;
};
int l=0,r=(int)h.size()-1;
while(l<r){
int m=(l+r)/2;
if(f(m)<=f(m+1)) r=m;
else l=m+1;
}
return f(l);
}
};
void slv(){
LL(n,m,q);
vector<ll> a(n),xs;
FOR(i,n){
in(a[i]);
a[i]%=m;
xs.push_back(a[i]);
}
vector<pair<int,ll>> qs(q);
FOR(i,q){
in(qs[i].fi,qs[i].se);
qs[i].fi--;
qs[i].se%=m;
xs.push_back(qs[i].se);
}
sort(all(xs));
xs.erase(unique(all(xs)),xs.end());
auto id=[&](ll x){
return int(lower_bound(all(xs),x)-xs.begin());
};
int K=xs.size(),B=max(1,(int)(2*sqrt(K)));
int nb=(K+B-1)/B;
vector<int> c(K),lazyC(nb);
vector<ll> p(K),lazyP(nb);
vector<LowerHull> hull(nb);
FOR(i,n) c[id(a[i])]++;
ll S=0,D=0;
int cnt=0;
FOR(i,K){
int f=c[i];
D+=(ll)((i128)f*((i128)cnt*xs[i]-S));
S+=(ll)f*xs[i];
cnt+=f;
c[i]=cnt;
p[i]=S;
}
auto rebuild=[&](int b){
hull[b].h.clear();
FOR(i,b*B,min(K,(b+1)*B)) hull[b].add(c[i],(i128)2*n*p[i]-(i128)m*c[i]*c[i]);
};
auto suffix=[&](int i,int dc,ll dp){
int b=i/B;
if(i%B){
FOR(j,i,min(K,(b+1)*B)){
c[j]+=dc;
p[j]+=dp;
}
rebuild(b++);
}
for(;b<nb;b++){
lazyC[b]+=dc;
lazyP[b]+=dp;
}
};
FOR(b,nb) rebuild(b);
for(auto [i,x] : qs){
ll old=a[i];
if(old!=x){
int u=id(old),v=id(x);
ll cu=c[u]+lazyC[u/B],pu=p[u]+lazyP[u/B];
ll cv=c[v]+lazyC[v/B],pv=p[v]+lazyP[v/B];
int t=(old<=x);
i128 dec=(i128)old*(2*cu-n)+S-2*pu;
i128 inc=(i128)x*(2*(cv-t)-(n-1))+S-old-2*(pv-t*old);
D+=(ll)(inc-dec);
suffix(u,-1,-old);
suffix(v,+1,x);
S+=x-old;
a[i]=x;
}
i128 k=(i128)n*m-2*S;
i128 best=(i128)1<<120;
FOR(b,nb){
ll dc=lazyC[b],dp=lazyP[b];
chmin(best,hull[b].query(k-(i128)2*m*dc)+(i128)2*n*dp-(i128)m*dc*dc+k*dc);
}
outln(D+(ll)best);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//in(t);
while(t--){
slv();
}
}