Copy.java

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Copy {
	static final int COPY = 1, QUERY = 2;
	static int currentVersion = 1;
	static int a[], b[];
	static int ans[] = new int[2];

	static class SegmentTree {
		Integer start, end, pos, version;
		SegmentTree left, right;

		public SegmentTree(int start, int end) {
			this.start = start;
			this.end = end;

			if (this.start != this.end) {
				int mid = this.start + (this.end - this.start) / 2;
				this.left = new SegmentTree(start, mid);
				this.right = new SegmentTree(mid + 1, end);
			}
		}

		public void update(int start, int end, int pos) {
			if (this.start == start && this.end == end) {
				this.pos = pos;
				this.version = currentVersion++;
			} else {
				int mid = this.start + (this.end - this.start) / 2;
				if (start <= mid)
					this.left.update(start, Math.min(end, mid), pos);
				if (mid < end)
					this.right.update(Math.max(mid + 1, start), end, Math.max(0, mid + 1 - start) + pos);
			}
		}
		
		public void query(int x) {
			if (this.start == x && this.end == x) {
				ans[0] = -1;
				ans[1] = -1;
				if (this.version != null) {
					ans[0] = this.version;
					ans[1] = this.pos;
				}
			} else {
				int mid = this.start + (this.end - this.start) / 2;
				if (x <= mid) {
					this.left.query(x);
					if (this.version != null && this.version > ans[0]) {
						ans[0] = this.version;
						ans[1] = (x - this.start) + this.pos;
					}					
				} else {
					this.right.query(x);
					if (this.version != null && this.version > ans[0]) {
						ans[0] = this.version;
						ans[1] = (x - this.start) + this.pos;
					}					
				}
			}			
		}
	}

	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(File f) {
			try {
				br = new BufferedReader(new FileReader(f));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		public FastScanner(InputStream f) {
			br = new BufferedReader(new InputStreamReader(f));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return null;
				st = new StringTokenizer(s);
			}
			return st.nextToken();
		}

		boolean hasMoreTokens() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return false;
				st = new StringTokenizer(s);
			}
			return true;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}
	}

	public static void main(String[] args) {
		FastScanner sc = new FastScanner(System.in);		
		int n = sc.nextInt(), m = sc.nextInt();
		
		a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();
		
		b = new int[n];
		for (int i = 0; i < n; i++)
			b[i] = sc.nextInt();
		
		SegmentTree tree = new SegmentTree(0, n - 1);
		for (int i = 0; i < m; i++) {
			int t = sc.nextInt();
			if (t == COPY) {
				int x = sc.nextInt(), y = sc.nextInt(), k = sc.nextInt();
				tree.update(y - 1, y + k - 2, x - 1);
			} else if (t == QUERY) {
				int x = sc.nextInt();
				tree.query(x - 1);
				if (ans[1] == -1)
					System.out.println(b[x - 1]);
				else
					System.out.println(a[ans[1]]);
			}
		}		
	}
}

This Segment Tree code solves this problem