首先可以证明，点积最值的点对都是都是在凸包上，套用题解的证明：假设里两个点都不在凸包上, 考虑把一个点换成凸包上的点(不动的那个点), 不管你是要点积最大还是最小, 你都可以把那个不动的点跟原点拉一条直线, 然后把所有的点投影到这条直线上, 要找的无非就是这条直线最前面或者最后面的两个点.这两个点不可能是不在凸包上的点.同理我们可以把另一个点移到凸包上.
由于数据随机生成，那么生成凸包上的点的个数的期望是logn，而且删的点落在凸包上的概率是logn/n，所以只需要对每次删点和加点暴力重构凸包即可。但是删点过程要求剩下的第k个还在的点，那么这就需要用平衡树去维护第k个点的值，直接用stl内部的红黑树。
// ——By DD_BOND #include<ext/pb_ds/assoc_container.hpp>
//#include<bits/stdc++.h>
//#include<unordered_map>
//#include<unordered_set>
#include<functional>
#include<algorithm>
#include<iostream>
//#include<ext/rope>
#include<iomanip>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<cstddef>
#include<cstdio>
#include<memory>
#include<vector>
#include<cctype>
#include<string>
#include<cmath>
#include<queue>
#include<deque>
#include<ctime>
#include<stack>
#include<map>
#include<set> #define fi first
#define se second
#define MP make_pair
#define pb push_back #pragma GCC optimize(3)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace std;
using namespace __gnu_pbds;
using Tree=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>; typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef unsigned long long ull; const int lim=1e9;
const ll LLMAX=2e18;
const int MAXN=2e5+;
const double eps=1e-;
const double pi=acos(-1.0);
const unsigned mul=;
const ll INF=0x3f3f3f3f3f3f3f3f; inline int dcmp(double x){
if(fabs(x)<eps) return ;
return (x>? : -);
} inline double sqr(double x){ return x*x; } Tree t; struct Point{
ll x,y; int id;
Point(){ x=,y=; }
Point(ll _x,ll _y):x(_x),y(_y){}
bool operator ==(const Point &b)const{
return x==b.x&&y==b.y;
}
bool operator <(const Point &b)const{
return (x-b.x)==? (y-b.y)< : x<b.x;
}
Point operator -(const Point &b)const{
return Point(x-b.x,y-b.y);
}
}; inline ll cross(Point a,Point b){ //叉积
return a.x*b.y-a.y*b.x;
} inline ll dot(Point a,Point b){ //点积
return a.x*b.x+a.y*b.y;
} Point tmp[MAXN];
int convex_hull(Point *p,int n,Point *ch){ //求凸包
int m=;
sort(p,p+n);
for(int i=;i<n;i++){
while(m>&&cross(tmp[m-]-tmp[m-],p[i]-tmp[m-])<=) m--;
tmp[m++]=p[i];
}
int k=m;
for(int i=n-;i>=;i--){
while(m>k&&cross(tmp[m-]-tmp[m-],p[i]-tmp[m-])<=) m--;
tmp[m++]=p[i];
}
if(n>) m--;
for(int i=;i<m;i++) ch[i]=tmp[i];
return m;
} class Magic{
public:
Magic(unsigned state):state(state),ans(){}
unsigned long long retrieve(){
unsigned modulo=0x7fffffff;
state=((unsigned long long)state*mul+ans)%modulo;
unsigned high=state;
state=((unsigned long long)state*mul+ans)%modulo;
return high*modulo+state;
}
int retrieve(int a,int b){
return (int)(retrieve()%(b-a+))+a;
}
void submit(unsigned k){
ans=ans*mul+k;
}
unsigned retrieveAns(){
return ans;
}
private:
unsigned state,ans;
}; class DataStructure{
public:
int n,m;
Point point[MAXN],rec[MAXN];
DataStructure(){ n=m=; }
void add(int x,int y){
t.insert(++m);
rec[m]=Point(x,y);
point[n]=Point(x,y);
point[n++].id=m;
n=convex_hull(point,n,point);
}
void erase(int r){
r=*t.find_by_order(r-);
t.erase(r);
for(int i=;i<n;i++)
if(point[i].id==r){
n=;
for(auto i:t) point[n]=rec[i],point[n++].id=i;
n=convex_hull(point,n,point);
break;
}
}
P query(){
P ans(,); ll len=LLMAX;
for(int i=;i<n;i++)
for(int j=;j<n;j++){
ll dis=dot(point[i],point[j]);
if(dis<len){
len=dis;
ans=P(point[i].id,point[j].id);
}
}
if(ans.fi>ans.se) swap(ans.fi,ans.se);
return ans;
}
}; int main(void){
int q; cin>>q;
for(int k=;k<q;++k){
t.clear();
unsigned state; string s; cin>>state>>s;
DataStructure ds; Magic magic(state);
for(char c:s){
if(c=='a'){
int x=magic.retrieve(-lim,lim);
int y=magic.retrieve(-lim,lim);
ds.add(x,y);
}
else if(c=='e'){
unsigned pos = magic.retrieve(,t.size());
ds.erase(pos);
}
else if(c=='q'){
auto best=ds.query();
magic.submit(best.first);
magic.submit(best.second);
}
}
cout<<magic.retrieveAns()<<endl;
}
}