public class Run {

	public static void main(String[] args) {
		Node<Integer> chain1 = buildChain1();
		Node<Integer> chain2 = buildChain2();

		printStack(tmpSol());

	}

	public static Stack<Integer> listsCompare(Node<Integer> pos1, Node<Integer> pos2) {
		Node<Integer> ps1 = pos1;
		Node<Integer> ps2 = pos2;

		Stack<Integer> stk = new Stack<Integer>();
		int n = Math.max(listsize(pos1), listsize(pos1));
		while (n > 0) {
			if (ps1 == null || ps2 == null)
				return stk;
			if (ps1.getValue() != ps2.getValue())
				return stk;

			stk.push(ps1.getValue());
			ps1 = ps1.getNext();
			ps2 = ps2.getNext();

			n--;
		}
		return stk;
	}

	public static Stack<Integer> tmpSol() {
		Node<Integer> lst1 = buildChain1();
		Node<Integer> lst2 = buildChain2();

		Stack<Integer> max_set_stk = new Stack<Integer>();
		Node<Integer> pos1 = lst1;
		Node<Integer> pos2 = lst2;
		Node<Integer> tmp1 = pos1;
		Node<Integer> tmp2 = pos2;
		while (pos2 != null) {
			tmp2 = pos2;

			while (pos1 != null) {
				boolean equality = false;

				if (pos1.getValue() == pos2.getValue()) {
					equality = true;
					tmp1 = pos1;
					Stack<Integer> tmp_stk = listsCompare(pos1, pos2);

					if (stackSize(max_set_stk) < stackSize(tmp_stk) ||
							max_set_stk.isEmpty()) {
						// empty previous stack values put newer
						while (!max_set_stk.isEmpty())
							max_set_stk.pop();
						while (!tmp_stk.isEmpty())
							max_set_stk.push(tmp_stk.pop());
					}
				}
				if(equality)
					pos1 = tmp1.getNext();
				else
					pos1 = pos1.getNext();
				pos2 = tmp2;
			}
			pos2 = pos2.getNext();
			pos1 = lst1;

		} // end while
			// printStack(max_set_stk);
		return max_set_stk;
	}

	// -------utils methods--------
	// prints the given chain
	public static void printChain(Node<Integer> first) {
		Node<Integer> tmp = first;
		while (tmp != null) {
			System.out.print(tmp.getValue() + "->");
			tmp = tmp.getNext();
		}
		System.out.print("->null");

	}

	// return size of given chain
	public static int listsize(Node<Integer> first) {
		Node<Integer> tmp = first;
		int size = 0;
		while (tmp.hasNext()) {
			size++;
			tmp = tmp.getNext();
		}
		return size + 1;
	}

	public static int stackSize(Stack<Integer> s) {
		int count = 0;
		Stack<Integer> tmp = new Stack<Integer>();
		if (s.isEmpty())
			return count;
		while (!s.isEmpty()) {
			tmp.push(s.pop());
			count++;
		}
		while (!tmp.isEmpty()) {
			s.push(tmp.pop());
		}
		return count;
	}

	public static void printStack(Stack<Integer> s) {
		Stack<Integer> tmp = new Stack<Integer>();
		while (!s.isEmpty()) {
			System.out.println("|_" + s.top() + "_|");

			tmp.push(s.pop());
		}
		while (!tmp.isEmpty()) {

			s.push(tmp.pop());
		}
	}

	public static Node<Integer> buildChain2() {
		Node<Integer> nd1 = new Node<Integer>(6);
		Node<Integer> nd2 = new Node<Integer>(3, nd1);
		Node<Integer> nd3 = new Node<Integer>(6, nd2);
		Node<Integer> nd4 = new Node<Integer>(5, nd3);
		Node<Integer> nd5 = new Node<Integer>(9, nd4);
		Node<Integer> nd6 = new Node<Integer>(8, nd5);
		Node<Integer> nd7 = new Node<Integer>(4, nd6);
		Node<Integer> nd8 = new Node<Integer>(4, nd7);
		Node<Integer> nd9 = new Node<Integer>(5, nd8);

		return nd9;
	}

	public static Node<Integer> buildChain1() {
		Node<Integer> nd1 = new Node<Integer>(7);
		Node<Integer> nd2 = new Node<Integer>(6, nd1);
		Node<Integer> nd3 = new Node<Integer>(3, nd2);
		Node<Integer> nd4 = new Node<Integer>(4, nd3);
		Node<Integer> nd5 = new Node<Integer>(5, nd4);
		Node<Integer> nd6 = new Node<Integer>(9, nd5);
		Node<Integer> nd7 = new Node<Integer>(8, nd6);
		Node<Integer> nd8 = new Node<Integer>(4, nd7);
		Node<Integer> nd9 = new Node<Integer>(3, nd8);
		Node<Integer> nd10 = new Node<Integer>(6, nd9);
		Node<Integer> nd11 = new Node<Integer>(5, nd10);
		Node<Integer> nd12 = new Node<Integer>(1, nd11);

		return nd12;
	}

}