This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/deque_operate_all_composite"
#include <iostream>
#include "../../data_structure/deque_aggregation.hpp"
#include "../../modint/modint.hpp"
using mint = ebi::modint998244353;
struct F {
mint a;
mint b;
};
F op(F f, F g) {
return {g.a * f.a, g.a * f.b + g.b};
}
int main() {
int q;
std::cin >> q;
ebi::deque_aggregation<F, op> swag;
while (q--) {
int t;
std::cin >> t;
if (t == 0) {
mint a, b;
std::cin >> a >> b;
swag.push_front({a, b});
} else if (t == 1) {
mint a, b;
std::cin >> a >> b;
swag.push_back({a, b});
} else if (t == 2) {
swag.pop_front();
} else if (t == 3) {
swag.pop_back();
} else {
mint x;
std::cin >> x;
if (swag.empty()) {
std::cout << x << '\n';
continue;
}
auto f = swag.fold_all();
mint ans = f.a * x + f.b;
std::cout << ans << '\n';
}
}
}
#line 1 "test/data_structure/Deque_Operate_All_Composite.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/deque_operate_all_composite"
#include <iostream>
#line 2 "data_structure/deque_aggregation.hpp"
#include <cassert>
#include <stack>
namespace ebi {
template <class Semigroup, Semigroup (*op)(Semigroup, Semigroup)>
struct deque_aggregation {
private:
struct Node {
Semigroup val;
Semigroup fold;
};
void move_front() {
assert(_front.empty());
int sz = _back.size();
std::stack<Semigroup> buff;
for (int i = 0; i < sz / 2; i++) {
buff.push(_back.top().val);
_back.pop();
}
while (!_back.empty()) {
Semigroup x = _back.top().val;
_back.pop();
push_front(x);
}
while (!buff.empty()) {
Semigroup x = buff.top();
buff.pop();
push_back(x);
}
}
void move_back() {
assert(_back.empty());
int sz = _front.size();
std::stack<Semigroup> buff;
for (int i = 0; i < sz / 2; i++) {
buff.push(_front.top().val);
_front.pop();
}
while (!_front.empty()) {
Semigroup x = _front.top().val;
_front.pop();
push_back(x);
}
while (!buff.empty()) {
Semigroup x = buff.top();
buff.pop();
push_front(x);
}
}
public:
deque_aggregation() = default;
int size() const {
return _front.size() + _back.size();
}
bool empty() const {
return size() == 0;
}
Semigroup front() {
assert(!empty());
if (_front.empty()) move_front();
return _front.top().val;
}
Semigroup back() {
assert(!empty());
if (_back.empty()) move_back();
return _back.top().val;
}
void push_front(Semigroup x) {
Node node = {x, x};
if (!_front.empty()) {
node.fold = op(x, _front.top().fold);
}
_front.push(node);
}
void push_back(Semigroup x) {
Node node = {x, x};
if (!_back.empty()) {
node.fold = op(_back.top().fold, x);
}
_back.push(node);
}
void pop_back() {
assert(!empty());
if (_back.empty()) move_back();
_back.pop();
}
void pop_front() {
assert(!empty());
if (_front.empty()) move_front();
_front.pop();
}
Semigroup fold_all() {
assert(!empty());
if (_front.empty()) {
return _back.top().fold;
} else if (_back.empty()) {
return _front.top().fold;
} else {
return op(_front.top().fold, _back.top().fold);
}
}
private:
std::stack<Node> _front, _back;
};
} // namespace ebi
#line 2 "modint/modint.hpp"
#line 5 "modint/modint.hpp"
#line 2 "modint/base.hpp"
#include <concepts>
#line 5 "modint/base.hpp"
#include <utility>
namespace ebi {
template <class T>
concept Modint = requires(T a, T b) {
a + b;
a - b;
a * b;
a / b;
a.inv();
a.val();
a.pow(std::declval<long long>());
T::mod();
};
template <Modint mint> std::istream &operator>>(std::istream &os, mint &a) {
long long x;
os >> x;
a = x;
return os;
}
template <Modint mint>
std::ostream &operator<<(std::ostream &os, const mint &a) {
return os << a.val();
}
} // namespace ebi
#line 7 "modint/modint.hpp"
namespace ebi {
template <int m> struct static_modint {
private:
using modint = static_modint;
public:
static constexpr int mod() {
return m;
}
static constexpr modint raw(int v) {
modint x;
x._v = v;
return x;
}
constexpr static_modint() : _v(0) {}
template <std::signed_integral T> constexpr static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <std::unsigned_integral T> constexpr static_modint(T v) {
_v = (unsigned int)(v % umod());
}
constexpr unsigned int val() const {
return _v;
}
constexpr unsigned int value() const {
return val();
}
constexpr modint &operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
constexpr modint &operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
constexpr modint operator++(int) {
modint res = *this;
++*this;
return res;
}
constexpr modint operator--(int) {
modint res = *this;
--*this;
return res;
}
constexpr modint &operator+=(const modint &rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
constexpr modint &operator-=(const modint &rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
constexpr modint &operator*=(const modint &rhs) {
unsigned long long x = _v;
x *= rhs._v;
_v = (unsigned int)(x % (unsigned long long)umod());
return *this;
}
constexpr modint &operator/=(const modint &rhs) {
return *this = *this * rhs.inv();
}
constexpr modint operator+() const {
return *this;
}
constexpr modint operator-() const {
return modint() - *this;
}
constexpr modint pow(long long n) const {
assert(0 <= n);
modint x = *this, res = 1;
while (n) {
if (n & 1) res *= x;
x *= x;
n >>= 1;
}
return res;
}
constexpr modint inv() const {
assert(_v);
return pow(umod() - 2);
}
friend modint operator+(const modint &lhs, const modint &rhs) {
return modint(lhs) += rhs;
}
friend modint operator-(const modint &lhs, const modint &rhs) {
return modint(lhs) -= rhs;
}
friend modint operator*(const modint &lhs, const modint &rhs) {
return modint(lhs) *= rhs;
}
friend modint operator/(const modint &lhs, const modint &rhs) {
return modint(lhs) /= rhs;
}
friend bool operator==(const modint &lhs, const modint &rhs) {
return lhs.val() == rhs.val();
}
friend bool operator!=(const modint &lhs, const modint &rhs) {
return !(lhs == rhs);
}
private:
unsigned int _v = 0;
static constexpr unsigned int umod() {
return m;
}
};
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
} // namespace ebi
#line 7 "test/data_structure/Deque_Operate_All_Composite.test.cpp"
using mint = ebi::modint998244353;
struct F {
mint a;
mint b;
};
F op(F f, F g) {
return {g.a * f.a, g.a * f.b + g.b};
}
int main() {
int q;
std::cin >> q;
ebi::deque_aggregation<F, op> swag;
while (q--) {
int t;
std::cin >> t;
if (t == 0) {
mint a, b;
std::cin >> a >> b;
swag.push_front({a, b});
} else if (t == 1) {
mint a, b;
std::cin >> a >> b;
swag.push_back({a, b});
} else if (t == 2) {
swag.pop_front();
} else if (t == 3) {
swag.pop_back();
} else {
mint x;
std::cin >> x;
if (swag.empty()) {
std::cout << x << '\n';
continue;
}
auto f = swag.fold_all();
mint ans = f.a * x + f.b;
std::cout << ans << '\n';
}
}
}