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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
const int N = 39989;
const int NN = 1000000000;
int Read() {
	int r = 0, k = 1; char c = getchar();
	for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r * k;
}
int lstans = 0; double maxans;
const int maxn = 40000;
int id[maxn << 2], A[maxn << 2], B[maxn << 2], C[maxn << 2], D[maxn << 2];
int decodeX(int x) { return (x + lstans - 1) % N + 1; }
int decodeY(int y) { return (y + lstans - 1) % NN + 1; }
double calc(int x0, int y0, int x1, int y1, int pos) {
	return double(y0) + double(pos - x0) / double(x0 - x1) * double(y0 - y1);
}
double cross(int x0, int y0, int x1, int y1, int x2, int y2, int x3, int y3) {
	double k1 = double(y0 - y1) / double(x0 - x1),
		   b1 = double(y0) - double(x0 * double(y0 - y1)) / double(x0 - x1),
		   k2 = double(y2 - y3) / double(x2 - x3),
		   b2 = double(y2) - double(x2 * double(y2 - y3)) / double(x2 - x3);
	return (b2 - b1) / (k1 - k2);
}
void change(int now, int l, int r, int x0, int y0, int x1, int y1, int nid) {
	if (x0 <= l && r <= x1) {
		if (!id[now]) {
			id[now] = nid;
			A[now] = x0;
			B[now] = y0;
			C[now] = x1;
			D[now] = y1;
			return;
		}
		double l1 = calc(A[now], B[now], C[now], D[now], l),
			   r1 = calc(A[now], B[now], C[now], D[now], r),
			   l2 = calc(x0, y0, x1, y1, l),
			   r2 = calc(x0, y0, x1, y1, r);
		if (l2 <= l1 && r2 <= r1) return;
		if (l1 < l2 && r1 < r2) {
			id[now] = nid;
			A[now] = x0;
			B[now] = y0;
			C[now] = x1;
			D[now] = y1;
			return;
		}
		double crs = cross(A[now], B[now], C[now], D[now], x0, y0, x1, y1);
		int mid = (l + r) >> 1;
		if (crs <= double(mid)) {
			if (l1 < l2)
				change(now << 1, l, mid, x0, y0, x1, y1, nid);
			if (r1 < r2) {
				swap(A[now], x0);
				swap(B[now], y0);
				swap(C[now], x1);
				swap(D[now], y1);
				swap(id[now], nid);
				change(now << 1, l, mid, x0, y0, x1, y1, nid);
			}
		} else {
			if (r1 < r2)
				change(now << 1 | 1, mid + 1, r, x0, y0, x1, y1, nid);
			if (l1 < l2) {
				swap(A[now], x0);
				swap(B[now], y0);
				swap(C[now], x1);
				swap(D[now], y1);
				swap(id[now], nid);
				change(now << 1 | 1, mid + 1, r, x0, y0, x1, y1, nid);
			}
		}
		return;
	} else {
		int mid = (l + r) >> 1;
		if (x0 <= mid)
			change(now << 1, l, mid, x0, y0, x1, y1, nid);
		if (x1 > mid)
			change(now << 1 | 1, mid + 1, r, x0, y0, x1, y1, nid);
	}
}
void query(int now, int l, int r, int pos) {
	if (id[now]) {
		if (!lstans) {
			lstans = id[now];
			maxans = calc(A[now], B[now], C[now], D[now], pos);
		} else {
			double tmp = calc(A[now], B[now], C[now], D[now], pos);
			if (tmp > maxans) {
				lstans = id[now];
				maxans = calc(A[now], B[now], C[now], D[now], pos);
			}
		}
	}
	if (l == r) return;
	int mid = (l + r) >> 1;
	if (pos <= mid) query(now << 1, l, mid, pos);
	else query(now << 1 | 1, mid + 1, r, pos);
}
int main() {
	int m = Read();
	int a, b, c, d, e, i = 0;
	while (m--) {
		e = Read();
		if (e) {
			++i;
			a = decodeX(Read());
			b = decodeY(Read());
			c = decodeX(Read());
			d = decodeY(Read());
			if (a > c) {
				swap(a, c);
				swap(b, d);
			}
			change(1, 1, N, a, b, c, d, i);
		} else {
			a = decodeX(Read());
			lstans = 0;
			query(1, 1, N, a);
			printf("%d\n", lstans);
		}
	}
	return 0;
}