#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define N          200
#define MODULO   98999

static int s[N + 1][N + 1], S[N + 1][N + 1];

int sitrling_main() {
	freopen("stirling.in", "r", stdin);
	freopen("stirling.out", "w", stdout);

	memset(s, 0, sizeof(s));
	memset(S, 0, sizeof(S));

	s[1][1] = 1;
	S[1][1] = 1;

	int i, j;

	for (i = 2; i <= N; i++) {
		for (j = 1; j <= i; j++) {
			s[i][j] = (s[i - 1][j - 1] - (i - 1) * s[i - 1][j]) % MODULO;
			S[i][j] = (S[i - 1][j - 1] + j * S[i - 1][j]) % MODULO;
		}
	}

	int T;
	scanf("%d\n", &T);

	for (i = 0; i < T; i++) {
		int x, n, m;
		scanf("%d %d %d\n", &x, &n, &m);
		if (x == 1) {
			printf("%d\n", s[n][m]);
		} else if (x == 2) {
			printf("%d\n", S[n][m]);
		}
	}

	return 0;
}

typedef struct uf_node_ {
	int rank;
	struct uf_node_ *parent;
} uf_node;

uf_node *new_node() {
	uf_node *node = (uf_node *) malloc(sizeof(uf_node));
	node->rank = 0;
	node->parent = node;
	return node;
}

uf_node *data[100001];

void do_union(int x, int y) {
	uf_node *nx = data[x];

	while (nx != nx->parent)
		nx = nx->parent;

	uf_node *ny = data[y];

	while (ny != ny->parent)
		ny = ny->parent;

	if (nx->rank < ny->rank) {
		nx->parent = ny;
		ny->rank++;
	} else {
		ny->parent = nx;
		nx->rank++;
	}
}

int do_find(int x, int y) {
	uf_node *nx = data[x];

	while (nx != nx->parent)
		nx = nx->parent;

	uf_node *ny = data[y];

	while (ny != ny->parent)
		ny = ny->parent;

	return nx == ny;
}

int union_find_main() {
	freopen("disjoint.in", "r", stdin);
	freopen("disjoint.out", "w", stdout);

	int n, m, i;
	int cod, x, y;
	scanf("%d %d\n", &n, &m);

	for (i = 1; i <= n; i++) {
		data[i] = new_node();
	}

	for (i = 1; i <= m; i++) {
		scanf("%d %d %d\n", &cod, &x, &y);
		if (cod == 1) {
			do_union(x, y);
		} else if (cod == 2) {
			int result = do_find(x, y);
			if (result)
				printf("DA\n");
			else
				printf("NU\n");
		}
	}

	return 0;
}

static char str[100001], *it;

static int termen();
static int factor();

static int eval() {
	int result = termen();
	while (*it == '+' || *it == '-') {
		if (*it == '+') {
			it++;
			result += termen();
		} else if (*it == '-') {
			it++;
			result -= termen();
		}
	}
	return result;
}

int termen() {
	int result = factor();
	while (*it == '*' || *it == '/') {
		if (*it == '*') {
			it++;
			result *= factor();
		} else if (*it == '/') {
			it++;
			result /= factor();
		}
	}
	return result;
}

int factor() {
	int result;
	if (*it == '(') {
		it++;
		result = eval();
		it++;
	} else {
		result = 0;
		while (*it >= '0' && *it <= '9') {
			result = result * 10 + *it - '0';
			it++;
		}
	}
	return result;
}

int evaluare_main() {
	freopen("evaluare.in", "r", stdin);
	freopen("evaluare.out", "w", stdout);

	fgets(str, 100001, stdin);

	int len = strlen(str);
	if (str[len - 1] == '\n') {
		str[len - 1] = 0;
		len--;
	}
	it = str;
	int result = eval();

	printf("%d\n", result);

	return 0;
}

void doprint(int i, long *pre, long *data) {
	if (i == -1)
		return;

	doprint(pre[i], pre, data);
	printf("%ld ", data[i]);
}

void print(int i, long *pre, long *data) {
	if (i == 0)
		return;

	print(pre[i], pre, data);
	printf("%d ", data[i]);
}

int scmax_main() {
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);

	static long data[100010];
	static long M[100010];
	static long pre[100010];

	int nr;
	scanf("%d\n", &nr);

	int i, j;
	for (i = 1; i <= nr; i++) {
		scanf("%ld ", &data[i]);
	}

	int L = 0, inf, sup, mid;
	memset(M, 0, sizeof(M));
	for (i = 1; i <= nr; i++) {
		inf = 1;
		sup = L;
		j = 0;
		if (data[M[L]] < data[i]) {
			j = L;
		} else {
			while (inf <= sup) {
				mid = inf + (sup - inf) / 2;
				if (data[M[mid]] < data[i]) {
					if (data[M[mid + 1]] > data[i]) {
						j = mid;
						break;
					}
					inf = mid + 1;
				} else {
					sup = mid - 1;
				}
			}
		}

		pre[i] = M[j];
		if (j == L || data[i] < data[M[j + 1]]) {
			M[j + 1] = i;
			if (L < (j + 1)) {
				L = j + 1;
			}
		}
	}

	printf("%d\n", L);
	print(M[L], pre, data);
	//for (i = 1; i <= nr; i++) {
	//	printf("%d %ld %d\n", i, data[i], pre[i]);
	//}

	/*
	 static long S[100000]
	 int bestS, bestJ;
	 S[0] = 1;
	 pre[0] = -1;
	 for (i = 1; i < nr; i++) {
	 bestS = 0;
	 bestJ = -1;
	 for (j = 0; j < i; j++) {
	 if (data[j] < data[i]) {
	 if (bestS < S[j]) {
	 bestS = S[j];
	 bestJ = j;
	 }
	 }

	 }
	 S[i] = 1 + bestS;
	 pre[i] = bestJ;
	 }

	 int maxS = S[0], maxI = 0;
	 for (i = 1; i < nr; i++) {
	 if (maxS < S[i]) {
	 maxS = S[i];
	 maxI = i;
	 }
	 }

	 printf("%d\n", maxS);
	 doprint(maxI, pre, data);
	 */
	return 0;
}

char B[2000010];
char A[2000010];

int strmatch_main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	fgets(A, 2000010, stdin);
	fgets(B, 2000010, stdin);

	int nA = strlen(A);
	if (A[nA - 1] == '\n') {
		nA--;
		A[nA] = 0;
	}

	int nB = strlen(B);
	if (B[nB - 1] == '\n') {
		nB--;
		B[nB] = 0;
	}

	if (nA > nB) {
		printf("0\n");
		return 0;
	}

	int i = nA, j, ok;
	int hA1 = 0, hA2 = 0, hB1 = 0, hB2 = 0;
	int P = 73, MOD1 = 100007, MOD2 = 100021;
	int P1 = 1, P2 = 1;
	for (i = 0; i < nA; i++) {
		hA1 = (hA1 * P + A[i]) % MOD1;
		hA2 = (hA2 * P + A[i]) % MOD2;

		hB1 = (hB1 * P + B[i]) % MOD1;
		hB2 = (hB2 * P + B[i]) % MOD2;

		if (i > 0) {
			P1 = (P1 * P) % MOD1;
			P2 = (P2 * P) % MOD2;
		}
	}

	int nsols = 0;
	int pos[1000];

	while (1) {
		if (hA1 == hB1 && hA2 == hB2) {
			if (nsols < 1000)
				pos[nsols] = i - nA;
			nsols++;
		}

		if (i < nB) {
			hB1 = ((hB1 - (B[i - nA] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;
			hB2 = ((hB2 - (B[i - nA] * P2) % MOD2 + MOD2) * P + B[i]) % MOD2;
			i++;
		} else {
			break;
		}
	}

	printf("%d\n", nsols);
	for (i = 0; i < nsols && i < 1000; i++)
		printf("%d ", pos[i]);

	return 0;
}

static int prev[2000010];

void initprev(char *p, int m) {
	int q, k;

	k = 0;
	prev[1] = 0;
	for (q = 2; q <= m; q++) {
		while (k > 0 && p[k + 1] != p[q]) {
			k = prev[k];
		}
		if (p[k + 1] == p[q])
			k++;
		prev[q] = k;
	}
}

void kmp(char *A, int m, char *B, int n) {
	int i;
	int q;
	int c = 0;
	static int res[1000];

	initprev(A, m);
	q = 0;

	for (i = 1; i <= n; i++) {
		while (q > 0 && A[q + 1] != B[i])
			q = prev[q];
		if (A[q + 1] == B[i])
			q++;
		if (q == m) {
			q = prev[q];
			if (c < 1000) {
				res[c] = i - m;
			}
			c++;
		}
	}

	printf("%d\n", c);
	for (i = 0; i < c; i++)
		printf("%d ", res[i]);
}

int kmp_main() {
	freopen("strmatch.in", "r", stdin);
	//freopen("grader_test50.in", "r", stdin);
	//freopen("strmatch.out", "w", stdout);

	memset(B, 0, sizeof(B));
	memset(A, 0, sizeof(A));
	fgets(B + 1, 2000009, stdin);
	fgets(A + 1, 2000009, stdin);
	kmp(B, strlen(B + 1), A, strlen(A + 1));
	return 0;
}

/*
#define GC 10002

int graph[GC][GC];
int cFlow[GC][GC];
int cPath[GC], cPathLen = 0;
int bestRes = 0;
char used[GC];

int dfs(int node, int maxFlow, int nNodes);

int getMaxFlow(int nNodes) {
	int i, j;
	for (i = 0; i < nNodes; i++) {
		printf("%d => ", i);
		for (int j = 0; j < nNodes; j++) {
			printf("%d ", graph[i][j]);
		}
		printf("\n");
	}
	memset(cFlow, 0, sizeof(cFlow));
	memset(used, 0, sizeof(used));
	while (dfs(0, 1 << 30, nNodes) > 0)
		;
	return bestRes;
}

int dfs(int node, int maxFlow, int nNodes) {
	int i;
	if (node == nNodes - 1) {
		int prev = 0;
		for (i = 0; i < cPathLen; i++) {
			int val = cPath[i];
			if (val == prev) {
				continue;
			}
			cFlow[prev][val] += maxFlow;
			prev = val;
		}
		cFlow[prev][node] += maxFlow;
		bestRes += maxFlow;
		memset(used, 0, sizeof(used));
		return maxFlow;
	}

	cPath[cPathLen++] = node;
	used[node] = 1;
	for (i = 0; i < nNodes; i++) {
		if (i == node || used[i]) {
			continue;
		}
		if (graph[node][i] > cFlow[node][i]) {
			int tmp = graph[node][i] - cFlow[node][i];
			int res = dfs(i, maxFlow > tmp ? tmp : maxFlow, nNodes);
			if (res > 0) {
				cPathLen--;
				return res;
			}
		}
	}

	cPathLen--;
	return 0;
}

int matching_main() {
	freopen("cuplaj.in", "r", stdin);
	//freopen("cuplaj.out", "r", stdout);

	int n, m, e;

	scanf("%d %d %d\n", &n, &m, &e);

	memset(graph, 0, sizeof(graph));
	int i, u, v;
	for (i = 0; i < e; i++) {
		scanf("%d %d\n", &u, &v);
		graph[u][n + v] = 1;
	}

	for (i = 1; i <= n; i++) {
		graph[0][i] = 1;
	}

	for (i = 1; i <= m; i++) {
		graph[n + i][n + m + 1] = 1;
	}

	int result = getMaxFlow(n + m + 2);
	printf("%d\n", result);

	return 0;
}
*/

#define MAX_P 1000010
char fprim[MAX_P];
int prim[80000], np;

void calculate() {
	int i, j;

	for (i = 2; i < MAX_P; i++)
		fprim[i - 1] = 1;

	np = 0;
	for (i = 2; i < MAX_P; i++) {
		if (!fprim[i]) continue;
		for (j = 2 * i; j < MAX_P; j += i) {
			fprim[j] = 0;
		}
		prim[np++] = i;
	}
}

long long query(long long A, long long B) {
	// #number <= A that are primes with B
	int sets[30];
	int k = 0, d = 0;
	long long result = 0;

	while (B > 1) {
		if (B % prim[d] == 0) {
			sets[k++] = prim[d];
		}
		while (B % prim[d] == 0) {
			B /= prim[d];
		}

		if (prim[d] * prim[d] > B && B > 1) {
			sets[k++] = B;
			B = 1;
		}
		d++;
	}

	long long tmp;
	int i, j, counter, sign;
	for (j = 1; j < (1 << k); j++) {
		tmp = 1;
		counter = 0;
		for (i = 0; i < k; i++) {
			if ((1 << i) & j) {
				tmp = tmp * 1LL * sets[i];
				counter++;
			}
		}

		if (counter % 2 == 0)
			sign = -1;
		else
			sign = +1;

		result = result + 1LL * sign * A / tmp;
	}

	return A * 1LL - result;
}

void pinex_main() {
	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);

	int i, M;
	long long A, B;
	scanf("%d\n", &M);

	calculate();

	for (i = 0; i < M; i++) {
		scanf("%lld %lld\n", &A, &B);
		long long result = query(A, B);
		printf("%lld\n", result);
	}
}

void nim_main() {
	freopen("nim.in", "r", stdin);
	freopen("nim.out", "w", stdout);

	int t, i, n, j, sum, tmp;
	scanf("%d\n", &t);
	for (i = 0; i < t; i++) {
		scanf("%d\n", &n);
		sum = 0;
		for (j = 0; j < n; j++) {
			scanf("%d ", &tmp);
			sum ^= tmp;
		}

		if (sum) printf("DA\n");
		else printf("NU\n");
	}
}

typedef struct point_t {
	int x;
	int y;
} point;

double getDistance(point *p1, point *p2) {
	return (double) (p1->x - p2->x) * (p1->x - p2->x) + (double) (p1->y - p2->y) * (p1->y - p2->y);
}

int compare_points(const void *o1, const void *o2) {
	const point **p1 = (const point **) o1, **p2 = (const point **) o2;
	if ((*p1)->x != (*p2)->x)
		return (*p1)->x - (*p2)->x;
	return (*p1)->y - (*p2)->y;
}

double getClosestPoints(point **points, int inf, int sup) {
	int i, j, c1, c2;
	double distance = 2e+20, tmp;

	if ((sup - inf) <= 3) {
        for (i = inf; i < sup; i++) {
            for (j = i + 1; j <= sup; j++) {
            	tmp = getDistance(points[i], points[j]);
                distance = distance > tmp ? tmp : distance;
            }
        }
	}
	else {
		int mid = inf + (sup - inf) / 2;

		double d1 = getClosestPoints(points, inf, mid);
		double d2 = getClosestPoints(points, mid + 1, sup);

		distance = d1 > d2 ? d2 : d1;

		for (i = mid, c1 = 0; c1 < 8 && i >= inf; i--, c1++) {
			for (j = mid + 1, c2 = 0; c2 < 8 && j <= sup; j++, c2++) {
				tmp = getDistance(points[i], points[j]);
                distance = distance > tmp ? tmp : distance;
			}
		}
	}

	return distance;
}

void cmap_main() {
	freopen("cmap.in", "r", stdin);
	freopen("cmap.out", "w", stdout);

	int i, n, x, y;
	scanf("%d\n", &n);

	point **points = (point **) malloc(n * sizeof(point *));
	for (i = 0; i < n; i++) {
		points[i] = (point *) malloc(sizeof(point));
		scanf("%d %d\n", &x, &y);
		points[i]->x = x;
		points[i]->y = y;
	}

	qsort(points, n, sizeof(point *), compare_points);

	double result = getClosestPoints(points, 0, n - 1);
	printf("%lf\n", sqrt(result));
}

int trees[2 * 100000];
volatile int g_a, g_b, g_key, g_maxim;

void construct_interval_tree(int id, int inf, int sup, int *data) {
	if (inf == sup) {
		trees[id] = data[inf];
		return;
	}

	int mid = (sup + inf) / 2;
	construct_interval_tree(2 * id + 1, inf, mid, data);

	if (mid == sup) {
		trees[id] = trees[2 * id + 1];
	}
	else {
		construct_interval_tree(2 * id + 2, mid + 1, sup, data);
		trees[id] = trees[2 * id + 1] > trees[2 * id + 2] ? trees[2 * id + 1] : trees[2 * id + 2];
	}
}

static void interval_tree_query(int id, int inf, int sup) {
	if (g_a <= inf && sup <= g_b) {
		if (g_maxim < trees[id]) {
			g_maxim = trees[id];
		}
		return;
	}

	int mid = (sup + inf) >> 1;
	if (g_a <= mid) {
		interval_tree_query(2 * id + 1, inf, mid);
	}
	if (g_b > mid) {
		interval_tree_query(2 * id + 2, mid + 1, sup);
	}
}

static void interval_tree_update(int id, int inf, int sup) {
	if (inf == sup) {
		trees[id] = g_key;
		return;
	}

	int mid = (sup + inf) >> 1;

	if (g_a <= mid) interval_tree_update(2 * id + 1, inf, mid);
	else interval_tree_update(2 * id + 2, mid + 1, sup);

	if (trees[2 * id + 1] && !trees[2 * id + 2]) {
		trees[id] = trees[2 * id + 1];
	}
	else {
		trees[id] = trees[2 * id + 1] > trees[2 * id + 2] ? trees[2 * id + 1] : trees[2 * id + 2];
	}
}

inline void arbint_main() {
	freopen("arbint.in", "r", stdin);
	freopen("arbint.out", "w", stdout);

	int n, m, i, op, a, b, result;
	static int data[100001];
	scanf("%d %d\n", &n, &m);

	for (i = 0; i < n; i++)
		scanf("%d ", &data[i]);

	for (i = 0; i < 2 * 100000; i++)
		trees[i] = NULL;
	construct_interval_tree(0, 0, n - 1, data);

	for (i = 0; i < m; i++) {
		scanf("%d %d %d\n", &op, &a, &b);
		a--;
		if (op == 0) {
			g_a = a;
			g_b = b - 1;
			g_maxim = -1;
			interval_tree_query(0, 0, n - 1);
			printf("%d\n", g_maxim);
		}
		else {
			g_a = a;
			g_b = a;
			g_key = b;
			interval_tree_update(0, 0, n - 1);
		}
	}
}

#define MAXN     100002
#define LOGMAXN      18

static void rmq_main() {
	long x, y, k, result;
	static int lg[LOGMAXN];
	static long A[MAXN];
	static int M[MAXN][LOGMAXN];
	long i, j;
	long n, m;

    freopen("rmq.in","r",stdin);
    freopen("rmq.out","w",stdout);

    scanf("%ld %ld\n", &n, &m);

    for (i = 0; i < n; i++)
        scanf("%ld ",&A[i]);

	for (i = 0; i < n; i++)
		M[i][0] = i;

	for (j = 1; 1 << j <= n; j++) {
		for (i = 0; i + (1 << (j - 1)) - 1 < n; i++) {
			if (A[M[i][j - 1]] <= A[M[i + (1 << (j - 1))][j - 1]]) {
				M[i][j] = M[i][j - 1];
			}
			else {
				M[i][j] = M[i + (1 << (j - 1))][j - 1];
			}
			//printf("[%d %d] %d | {%d, %d}\n", i, j, M[i][j], i, i + (1 << j) - 1);
		}
	}

	lg[1] = 0;
    for (i = 2; i <= n; i++) {
    	lg[i] = 1 + lg[i / 2];
    }

    int p;
    for (p = 1; p <= m; p++) {
        scanf("%ld %ld\n", &i, &j);
        i--; j--;
        k = lg[j - i];
        if (A[M[i][k]] <= A[M[j - (1 << k) + 1][k]]) {
        	result = M[i][k];
        }
        else {
        	result = M[j - (1 << k) + 1][k];
        }
        printf("%ld\n", A[result]);
    }
}

static int T[100010], L[100010];
static int P[100010][20];

int get_lca1(int n, int p, int q) {
	int tmp, i;

	if (L[p] < L[q]) {
		tmp = p;
		p = q;
		q = tmp;
	}

	int log;
	for (log = 1; (1 << log) <= L[p]; log++)
		;
	log--;

	for (i = log; i >= 0; i--) {
		if (L[p] - (1 << i) >= L[q])
			p = P[p][i];
	}

	if (p == q)
		return p;

	for (i = log; i >= 0; i--) {
		if (P[p][i] != -1 && P[p][i] != P[q][i]) {
			p = P[p][i];
			q = P[q][i];
		}
	}

	return T[p];
}

static void lca_main() {
	int n, m;

    freopen("lca.in","r",stdin);
    freopen("lca.out","w",stdout);

	scanf("%d %d\n", &n, &m);

	int i, j, tmp, u, v;

	T[1] = -1;
	L[1] = 0;
	for (i = 1; i < n; i++) {
		scanf("%d ", &tmp);
		T[i + 1] = tmp;
		L[i + 1] = 1 + L[tmp];
	}

	for (i = 1; i <= n; i++) {
		P[i][0] = T[i];
	}

	for (j = 1; (1 << j) <= n; j++) {
		for (i = 1; i <= n; i++)
			P[i][j] = P[P[i][j - 1]][j - 1];
	}

	for (i = 0; i < m; i++) {
		scanf("%d %d\n", &u, &v);
		tmp = get_lca1(n, u, v);
		printf("%d\n", tmp);
	}
}

#define MAXN 200000
int heap[MAXN], nh, key[MAXN], pos[MAXN], nk;

int heap_min() {
	if (nh <= 0)
		return -1;
	return key[heap[0]];
}

void heap_remove(int x) {
	int tmp, y = -1;
	while (x != y) {
		y = x;

        if (y * 2 + 1 < nh && key[heap[x]] > key[heap[y * 2 + 1]])
        	x = y * 2 + 1;
        if (y * 2 + 2 < nh && key[heap[x]] > key[heap[y * 2 + 2]])
        	x = y * 2 + 2;

        tmp = heap[x];
        heap[x] = heap[y];
        heap[y] = tmp;

        pos[heap[x]] = x;
        pos[heap[y]] = y;
	}
}

void heap_push(int x) {
	int it = x, tmp;

	while (it != -1 && key[heap[it]] < key[heap[(it - 1) / 2]]) {
		tmp = heap[it];
		heap[it] = heap[(it - 1) / 2];
		heap[(it - 1) / 2] = tmp;

		pos[heap[it]] = it;
		pos[heap[(it - 1) / 2]] = (it - 1) / 2;
		it = (it - 1) / 2;
	}
}

static void heap_main() {
    freopen("heapuri.in","r",stdin);
    freopen("heapuri.out","w",stdout);

    int ops, i, op, result, x, hpos;

    scanf("%d\n", &ops);

    nk = 0;
    nh = 0;

    for (i = 0; i < ops; i++) {
    	scanf("%d", &op);
    	if (op == 1) {
    		scanf(" %d\n", &x);

    		key[nk] = x;
    		heap[nh] = nk;
    		pos[nk] = nh;
    		nk++;
    		nh++;
    		heap_push(nh - 1);
    	}
    	else if (op == 2) {
    		scanf(" %d\n", &x);
    		x--;

    		key[x] = -1;
    		heap_push(pos[x]);
    		heap[0] = heap[--nh];
    		pos[heap[0]] = 0;
    		if (nh > 1)
    			heap_remove(0);
    	}
    	else if (op == 3) {
    		result = heap_min();
    		printf("%d\n", result);
    	}
    }
}

typedef struct ch_point_t {
	double x;
	double y;
} ch_point;

static ch_point g_points[120000];
double g_x, g_y;

double get_angle(const void *x) {
	const ch_point *p = (const ch_point *) x;
	if (p->x == g_x && p->y == g_y)
		return 0;

	if (p->x >= g_x)
		return asin((p->y - g_y) / (sqrt((p->x - g_x) * (p->x - g_x) + (p->y - g_y) * (p->y - g_y))));
	return M_PI - asin((p->y - g_y) / (sqrt((p->x - g_x) * (p->x - g_x) + (p->y - g_y) * (p->y - g_y))));
}

int convex_hull_compare(const void *x, const void *y) {
	double sin1 = get_angle(x);
	double sin2 = get_angle(y);

	if (sin1 < sin2)
		return -1;
	else if (sin1 > sin2)
		return 1;
	return 0;
}

static double cross_product(int p1, int p2, int p3) {
	double x1 = g_points[p1].x, x2 = g_points[p2].x, x3 = g_points[p3].x;
	double y1 = g_points[p1].y, y2 = g_points[p2].y, y3 = g_points[p3].y;
	return (y2 - y1) * (x3 - x1) - (y3 - y1) * (x2 - x1);
}

static void convex_hull_main() {
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);

    int n, i;
    static int stack[120000], stack_size = 0;
    scanf("%d\n", &n);
    for (i = 0; i < n; i++) {
    	scanf("%lf %lf\n", &g_x, &g_y);
    	g_points[i].x = g_x;
    	g_points[i].y = g_y;
    }

    g_x = g_points[0].x;
    g_y = g_points[0].y;
    for (i = 1; i < n; i++) {
    	if (g_y > g_points[i].y) {
    		g_x = g_points[i].x;
    		g_y = g_points[i].y;
    	}
    	else if (g_y == g_points[i].y && g_x > g_points[i].x) {
    		g_x = g_points[i].x;
    	}
    }

    qsort(g_points, n, sizeof(ch_point), convex_hull_compare);

    for (i = 0; i < n && stack_size < 3; i++) {
        stack[stack_size++] = i;
    }

    int x, y, z;

    for (; i < n; i++) {
    	x = stack[stack_size - 2];
    	y = stack[stack_size - 1];
    	z = i;
        while (cross_product(x, y ,z) >= 0 && stack_size > 2) {
        	stack_size--;
        	x = stack[stack_size - 2];
        	y = stack[stack_size - 1];
        }
        stack[stack_size++] = i;
    }

    printf("%d\n", stack_size);

    for (i = 0; i < stack_size; i++) {
    	printf("%lf %lf\n", g_points[stack[i]].x, g_points[stack[i]].y);
    }
}

static long aib[100001];

static void aib_update(int pos, long key, int n) {
	int it = 0;

	while (pos <= n) {
		aib[pos] += key;
		while ((pos & (1 << it)) == 0)
			it++;
		pos += (1 << it);
		it++;
	}
}

static long aib_query(int sup, int n) {
	long s = 0;
	int it = 0;

	while (sup > 0) {
		s += aib[sup];
		while ((sup & (1 << it)) == 0)
			it++;
		sup -= (1 << it);
		it++;
	}


	return s;
}

static int aib_min_pos(long sum, int n) {
	int i, step;

	for (step = 1; step <= n; step <<= 1) ;

	for (i = 0; step; step >>= 1) {
		if (i + step <= n) {
			if (sum >= aib[i + step]) {
				i += step;
				sum -= aib[i];
				if (!sum)
					return i;
			}
		}
	}

	return -1;
}

static void aib_main() {
	freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);

    int n, m;
    int i, op;
    long tmp, a, b;
    scanf("%d %d\n", &n, &m);

    memset(aib, 0, sizeof(aib));

    for (i = 1; i <= n; i++) {
    	scanf("%ld ", &tmp);
    	aib_update(i, tmp, n);
    }

    for (i = 1; i <= m; i++) {
    	scanf("%d ", &op);
    	if (op == 0) {
    		scanf("%ld %ld\n", &a, &b);
    		aib_update(a, b, n);
    	}
    	else if (op == 1) {
    		scanf("%ld %ld\n", &a, &b);
    		tmp = aib_query(b, n) - aib_query(a - 1, n);
    		printf("%ld\n", tmp);
    	}
    	else if (op == 2) {
    		scanf("%ld\n", &a);
    		tmp = aib_min_pos(a, n);
    		printf("%ld\n", tmp);
    	}
    }
}


int main(int argc, char **argv) {
	//stirling_main();
	//union_find_main();
	//evaluare_main();
	//scmax_main();
	//strmatch_main();
	//pinex_main();
	//nim_main();
	//cmap_main();
	//arbint_main();
	//rmq_main();
	//lca_main();
	//heap_main();
	convex_hull_main();
	//aib_main();

	//return kmp_main();
	//return matching_main();

	return 0;
}