Problem: Once upon a time in a kingdom far, far away… Okay, let’s start at the point where Ivan the Fool met Gorynych the Dragon. Ivan took out his magic sword and the battle began. First Gorynych had h heads and t tails. With each strike of the sword Ivan can either cut off several heads (from 1 to n, but not more than Gorynych has at the moment), or several tails (from 1 to m, but not more than Gorynych has at the moment). At the same time, horrible though it seems, Gorynych the Dragon can also grow new heads and tails. And the number of growing heads and tails is determined uniquely by the number of heads or tails cut by the current strike. When the total number of heads and tails exceeds R, Gorynych the Dragon strikes its final blow and destroys Ivan the Fool. That’s why Ivan aims to cut off all the dragon’s heads and tails as quickly as possible and win. The events can also develop in a third way: neither of the opponents can win over the other one and they will continue fighting forever.

The tale goes like this; easy to say, hard to do. Your task is to write a program that will determine the battle’s outcome. Consider that Ivan strikes consecutively. After each blow Gorynych grows a number of new heads and tails depending on the number of cut ones. Gorynych the Dragon is defeated if after the blow he loses all his heads and tails and can’t grow new ones. Ivan fights in the optimal way (fools are lucky), i.e. 

  * if Ivan can win, he wins having struck the least number of blows; 
  * if it is impossible to defeat Gorynych, but is possible to resist him for an infinitely long period of time, then that’s the strategy Ivan chooses; 
  * if Gorynych wins in any case, Ivan aims to resist him for as long as possible. 

Input

The first line contains three integers h, t and R (0 ≤ h, t, R ≤ 200, 0 < h + t ≤ R) which represent the initial numbers of Gorynych’s heads and tails and the largest total number of heads and tails with which Gorynych the Dragon does not yet attack. The next line contains integer n (1 ≤ n ≤ 200). The next n contain pairs of non-negative numbers "hi ti" which represent the number of heads and the number of tails correspondingly, that will grow if Gorynych has i heads (1 ≤ i ≤ n) cut. The next line contains an integer m (1 ≤ m ≤ 200) and then — the description of Gorynych’s behavior when his tails are cut off in the format identical to the one described above. All the numbers in the input file do not exceed 200. 

Output

Print "Ivan" (without quotes) in the first line if Ivan wins, or "Zmey" (that means a dragon in Russian) if Gorynych the Dragon wins. In the second line print a single integer which represents the number of blows Ivan makes. If the battle will continue forever, print in the first line "Draw".

Examples

Input

2 2 4
2
1 0
0 1
3
0 1
0 1
0 0


Output

Ivan
2


Input

2 2 4
1
0 1
1
1 0


Output

Draw


Input

2 2 5
1
1 1
1
3 0


Output

Zmey
2

Solution (in JAVA):

Solution:
import java.util.*;

public class Dragon{
	static ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
	public static void main(String[] args){
		Scanner reader = new Scanner(System.in);
		int h = reader.nextInt(); //initial heads
		int t = reader.nextInt(); //initial tails
		int r = reader.nextInt(); //deathly sum
		int n = reader.nextInt();
		
		int[] hcah = new int[n+1];
		int[] hcat = new int[n+1];
		
		for(int i = 1; i <= n; i++){
			hcah[i] = reader.nextInt();
			hcat[i] = reader.nextInt();
		}
		
		int m = reader.nextInt();
		int[] tcah = new int[m+1];
		int[] tcat = new int[m+1];
		
		for(int i = 1; i <= m; i++){
			tcah[i] = reader.nextInt();
			tcat[i] = reader.nextInt();
		}
		
		//build graph
		for(int i = 0; i < 201*201; i++){
			g.add(new ArrayList<Integer>());
			ArrayList<Integer> node = g.get(i);
			
			int tails = i%201;
			int heads = (i/201)%201;
			
			if(heads+tails > r)
				continue;
			
			for(int j = 1; j <= Math.min(heads, n); j++){
				if(heads - j + hcah[j] + tails + hcat[j] > r){
					node.add(e(100, 101));
				}else{
					node.add(e(heads - j + hcah[j], tails + hcat[j]));
				}
			}
			
			for(int j = 1; j <= Math.min(tails, m); j++){
				if(heads + tcah[j] + tails - j + tcat[j] > r){
					node.add(e(100, 101));
				}else{
					node.add(e(heads + tcah[j], tails - j + tcat[j]));
				}
			}
		}
		
		//search for cycle
		boolean draw = cycle(e(h,t), new boolean[201*201], new boolean[201*201]);
		//boolean draw = cycle(e(h,t), new boolean[201*201]);
		//System.out.println("done drawing");
		if(draw){
			//if cycle, bfs for win
			int win = bfs(e(h,t));
			if(win==-1){
				System.out.println("Draw");
			}else{
				System.out.println("Ivan");
				System.out.println(win);
			}
		}else{
			//else bfs for win and if none longest path on a dag
			int win = bfs(e(h,t));
			if(win==-1){
				LinkedList<Integer> res = sort(e(h,t));
				
				int[] memo = new int[201*201];
				Arrays.fill(memo,-1);
				
				while(!res.isEmpty()){
					p(res.removeLast(), memo);
				}
				
				System.out.println("Zmey");
				System.out.println(p(e(h,t), memo));
			}else{
				System.out.println("Ivan");
				System.out.println(win);
			}
		}
	}
	
	public static int p(int n, int[] memo){
		if(memo[n] == -1){
			int max = 0;
			for(Integer x:g.get(n)){
				max = Math.max(max, 1+p(x, memo));
			}
			memo[n] = max;
		}
		return memo[n];	
	}	
	
	public static LinkedList<Integer> sort(int s){
		LinkedList<Integer> q = new LinkedList<Integer>();
		
		int[] in = new int[201*201];
		
		for(ArrayList<Integer> x:g){
			for(Integer y:x){
				in[y]++;
			}
		}
		
		q.add(s);
		LinkedList<Integer> res = new LinkedList<Integer>();
		
		while(!q.isEmpty()){
			int cur = q.remove();
			res.add(cur);
			
			for(Integer x:g.get(cur)){
				in[x]--;
				
				if(in[x] == 0){
					q.add(x);
				}
			}
		}
		
		return res;
	}
	
	public static int bfs(int s){
		LinkedList<State> q = new LinkedList<State>();
		boolean[] visited = new boolean[g.size()];
		
		q.add(new State(s, 0));
		visited[s] = true;
		
		int search = -1;
		
		while(!q.isEmpty()){
			State cur = q.remove();
			
			if(cur.e == 0){
				search = cur.m;
				break;
			}
			
			for(Integer x:g.get(cur.e)){
				if(!visited[x]){
					q.add(new State(x, cur.m+1));
					visited[x] = true;
				}
			}
		}
		
		return search;
	}
	
	public static boolean cycle(int s, boolean[] visiting, boolean[] visited){
		visiting[s] = true;
		boolean good = false;
		
		for(Integer x:g.get(s)){
			if(visiting[x])
				good = true;
			else if(!visited[x]){
				good = good || cycle(x, visiting, visited);
			}
		}
		
		visiting[s] = false;
		visited[s] = true;
		return good;
	}
	
	/*public static boolean cycle(int s, boolean[] visited){
		visited[s] = true;
		//System.out.println("Searching in " + ((s/201)%201) + " " + s%201);
		boolean good = false;
		for(Integer x:g.get(s)){
			//System.out.println("Jumping to " + ((x/201)%201) + " " + x%201);
			good = good || dfs(x, s, new boolean[201*201]);
		}
		
		for(Integer x:g.get(s)){
			if(!visited[x])
				good = good || cycle(x, visited);
		}
		
		return good;
	}*/
	
	public static boolean dfs(int s, int t, boolean[] visited){
		visited[s] = true;
		
		if(s == t){
			//System.out.println("Found in cycle originating at " + ((s/201)%201) + " " + s%201);
			return true;
		}
		
		boolean good = false;
		for(Integer x:g.get(s)){
			if(!visited[x])
				good = good || dfs(x, t, visited);
		}
		
		return good;
	}
		
	//h|t
	public static int e(int h, int t){
		return h*201+t;
	}
	
	public static class State{
		int e,m;
		
		public State(int _e, int _m){
			e = _e;
			m = _m;
		}
	}
}