#include //#include //#include using namespace std; //using namespace __gnu_pbds; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #define watch(x) cout<<(#x)<<"="<<(x)<<'\n' #define mset(d,val) memset(d,val,sizeof(d)) #define cbug if(DEBUG) cout #define setp(x) cout< ii; typedef vector vi; typedef vector vii; //template //using pbds = tree, rb_tree_tag, tree_order_statistics_node_update>; void SD(int t=0){ cout<<"PASSED "< void amax(T &a, T b){ a=max(a,b); } template void amin(T &a, T b){ a=min(a,b); } struct Hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; const ll INF = ll(1e18); const int MOD = 998244353; const bool DEBUG = 0; const int MAXN = 100005; const int LG = 21; int main() { cin.tie(0)->sync_with_stdio(0); string s; cin>>s; cout<