1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| #include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <algorithm>
#define LL long long
#define FOR(i,A,B) for(int i=A;i<=B;i++)
#define BOR(i,A,B) for(int i=A;i>=B;i--)
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define INF 0x3f3f3f3f
#define MOD 998244353
#define FOR_SIDE(i,A) for(int i=Head[A];i;i=Next[i])
using namespace std;
const int MAXN=1e5+10,MAXM=1e6+10;
int Last,Total,Test;
int Next[MAXM<<1],End[MAXM<<1],Head[MAXN],Val[MAXM<<1],Kind[MAXM<<1],Cur;
int Root[MAXN],Dep[MAXN],Size[MAXN];
int Anc[MAXN][20],Min[MAXN][20],Dir[MAXN][20];
int u,v,w,Opt;
inline void File() {
freopen("money.in","r",stdin);
freopen("money.out","w",stdout);
}
inline void DFS(int New,int Pre,int Top) {
Root[New]=Top;
Dep[New]=Dep[Pre]+1;
FOR(i,1,17) {
Anc[New][i]=Anc[Anc[New][i-1]][i-1];
Min[New][i]=min(Min[New][i-1],Min[Anc[New][i-1]][i-1]);
Dir[New][i]=(Dir[New][i-1] | Dir[Anc[New][i-1]][i-1]);
}
FOR_SIDE(i,New) {
if(End[i]==Pre) continue;
Anc[End[i]][0]=New;
Min[End[i]][0]=Val[i];
Dir[End[i]][0]=(Kind[i] ^ 3);
DFS(End[i],New,Top);
}
}
inline void Add_Edge(int From,int To,int Temp) {
Next[++Cur]=Head[From];
Head[From]=Cur;
End[Cur]=To;
Val[Cur]=Temp;
Kind[Cur]=1;
Next[++Cur]=Head[To];
Head[To]=Cur;
End[Cur]=From;
Val[Cur]=Temp;
Kind[Cur]=2;
}
inline void Update(int From,int To,int Temp) {
Add_Edge(From,To,Temp);
int Base=1;
if(Size[Root[From]]>Size[Root[To]]) Base=2,swap(From,To);
Size[Root[To]]+=Size[Root[From]];
Anc[From][0]=To;
Min[From][0]=Temp;
Dir[From][0]=Base;
DFS(From,To,Root[To]);
}
inline int Get(int From,int To) {
int Base=1,Ans=INF;
if(Dep[From]<Dep[To]) Base=2,swap(From,To);
BOR(i,17,0)
if(Dep[From]-(1<<i)>=Dep[To]) {
if(Dir[From][i]!=Base) return 0;
Ans=min(Ans,Min[From][i]);
From=Anc[From][i];
}
if(From==To) return Ans;
BOR(i,17,0) {
if(Anc[From][i]!=Anc[To][i]) {
if(Dir[From][i]!=Base || Dir[To][i]!=(Base ^ 3)) return 0;
Ans=min(Ans,min(Min[From][i],Min[To][i]));
From=Anc[From][i];
To=Anc[To][i];
}
}
if(Dir[From][0]!=Base || Dir[To][0]!=(Base ^ 3)) return 0;
Ans=min(Ans,min(Min[From][0],Min[To][0]));
return Ans;
}
int main() {
File();
scanf("%d %d",&Total,&Test);
FOR(i,1,Total) Root[i]=i,Size[i]=1;
while(Test--) {
scanf("%d %d %d",&Opt,&u,&v);
u=(u+Last)%Total+1;
v=(v+Last)%Total+1;
if(Opt==0) {
scanf("%d",&w);
w=(w+Last)%Total+1;
Update(u,v,w);
} else { printf("%d\n",Last=Get(u,v)); }
}
return 0;
}
|