#include #define SIZE 500 #define NUM 400 void swap(int* a, int* b) { if (a == b) return; *a ^= *b; *b ^= *a; *a ^= *b; } typedef struct List { struct List *next; int u, w; } list; #define HASH 3001 const int H_Mod = HASH; int main() { int i, N, K, Q, A[200001], B[200001]; scanf("%d %d %d", &N, &K, &Q); for (i = 1; i <= K; i++) scanf("%d %d", &(A[K-i]), &(B[K-i])); int h, hn = 0, j, k = K / SIZE, tmp[400001], u, w; static list *hash[NUM][HASH] = {}, hd[SIZE * NUM * 2], *hp; for (j = 1; j <= N; j++) tmp[j] = j; for (i = 0; i <= k; i++) { for (j = 0; j < SIZE && j + i * SIZE < K; j++) swap(&(tmp[A[j+i*SIZE]]), &(tmp[B[j+i*SIZE]])); for (j = 0; j < SIZE && j + i * SIZE < K; j++) { w = A[j+i*SIZE]; if (tmp[w] != w) { u = tmp[w]; h = u % H_Mod; hd[hn].u = u; hd[hn].w = w; hd[hn].next = hash[i][h]; hash[i][h] = &(hd[hn++]); tmp[w] = w; } w = B[j+i*SIZE]; if (tmp[w] != w) { u = tmp[w]; h = u % H_Mod; hd[hn].u = u; hd[hn].w = w; hd[hn].next = hash[i][h]; hash[i][h] = &(hd[hn++]); tmp[w] = w; } } } int q, L, R, X; for (q = 1; q <= Q; q++) { scanf("%d %d %d", &L, &R, &X); L ^= R; R ^= L; L ^= R; L = K - L; R = K - R; for (j = L; j <= R && j % SIZE != 0; j++) { if (X == A[j]) X = B[j]; else if (X == B[j]) X = A[j]; } if (j <= R) { for (i = j / SIZE; (i + 1) * SIZE <= R; i++) { h = X % H_Mod; for (hp = hash[i][h]; hp != NULL; hp = hp->next) if (hp->u == X) break; if (hp != NULL) X = hp->w; } for (j = i * SIZE; j <= R; j++) { if (X == A[j]) X = B[j]; else if (X == B[j]) X = A[j]; } } printf("%d\n", X); } fflush(stdout); return 0; }