fork download
  1. import java.io.*;
  2. import java.math.*;
  3. import java.util.*;
  4. import java.lang.*;
  5.  
  6.  
  7.  
  8.  
  9. // Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
  10.  
  11. public final class Main {
  12. static class Reader
  13. {
  14. final private int BUFFER_SIZE = 1 << 16;
  15. private DataInputStream din;
  16. private byte[] buffer;
  17. private int bufferPointer, bytesRead;
  18.  
  19. public Reader()
  20. {
  21. din = new DataInputStream(System.in);
  22. buffer = new byte[BUFFER_SIZE];
  23. bufferPointer = bytesRead = 0;
  24. }
  25.  
  26. public Reader(String file_name) throws IOException
  27. {
  28. din = new DataInputStream(new FileInputStream(file_name));
  29. buffer = new byte[BUFFER_SIZE];
  30. bufferPointer = bytesRead = 0;
  31. }
  32.  
  33. public String readLine() throws IOException
  34. {
  35. byte[] buf = new byte[64]; // line length
  36. int cnt = 0, c;
  37. while ((c = read()) != -1)
  38. {
  39. if (c == '\n')
  40. break;
  41. buf[cnt++] = (byte) c;
  42. }
  43. return new String(buf, 0, cnt);
  44. }
  45.  
  46. public int nextInt() throws IOException
  47. {
  48. int ret = 0;
  49. byte c = read();
  50. while (c <= ' ')
  51. c = read();
  52. boolean neg = (c == '-');
  53. if (neg)
  54. c = read();
  55. do
  56. {
  57. ret = ret * 10 + c - '0';
  58. } while ((c = read()) >= '0' && c <= '9');
  59.  
  60. if (neg)
  61. return -ret;
  62. return ret;
  63. }
  64.  
  65. public long nextLong() throws IOException
  66. {
  67. long ret = 0;
  68. byte c = read();
  69. while (c <= ' ')
  70. c = read();
  71. boolean neg = (c == '-');
  72. if (neg)
  73. c = read();
  74. do {
  75. ret = ret * 10 + c - '0';
  76. }
  77. while ((c = read()) >= '0' && c <= '9');
  78. if (neg)
  79. return -ret;
  80. return ret;
  81. }
  82.  
  83. public double nextDouble() throws IOException
  84. {
  85. double ret = 0, div = 1;
  86. byte c = read();
  87. while (c <= ' ')
  88. c = read();
  89. boolean neg = (c == '-');
  90. if (neg)
  91. c = read();
  92.  
  93. do {
  94. ret = ret * 10 + c - '0';
  95. }
  96. while ((c = read()) >= '0' && c <= '9');
  97.  
  98. if (c == '.')
  99. {
  100. while ((c = read()) >= '0' && c <= '9')
  101. {
  102. ret += (c - '0') / (div *= 10);
  103. }
  104. }
  105.  
  106. if (neg)
  107. return -ret;
  108. return ret;
  109. }
  110.  
  111. private void fillBuffer() throws IOException
  112. {
  113. bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  114. if (bytesRead == -1)
  115. buffer[0] = -1;
  116. }
  117.  
  118. private byte read() throws IOException
  119. {
  120. if (bufferPointer == bytesRead)
  121. fillBuffer();
  122. return buffer[bufferPointer++];
  123. }
  124.  
  125. public void close() throws IOException
  126. {
  127. if (din == null)
  128. return;
  129. din.close();
  130. }
  131. }
  132. public static void main(String args[] ) throws Exception {
  133.  
  134. //StringBuffer st = new StringBuffer();
  135. // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  136. // StringTokenizer st1 = new StringTokenizer(br.readLine());
  137. // InputStream inputStream = System.in;
  138. OutputStream outputStream = System.out;
  139. // InputReader s = new InputReader(inputStream);
  140. PrintWriter out = new PrintWriter(outputStream);
  141. //BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
  142. Reader s = new Reader();
  143. int n = s.nextInt();;
  144. int m = s.nextInt();;
  145. int k = s.nextInt();;
  146. int p=1000000007;
  147. long[][] g = new long[n][n];
  148. while(m-->0){
  149. //st1 = new StringTokenizer(br.readLine());
  150. int a = s.nextInt();;
  151. int b = s.nextInt();;
  152. g[a-1][b-1]++;
  153. }
  154. g = mmodexpo(g,k,p);
  155. //st.append(g[1][n]);
  156. out.print(g[0][n-1]);
  157. out.close();
  158. }
  159. public static long[][] mmodexpo(long[][] x,int y,int p){
  160. long[][] res = new long[x.length][x.length];
  161. // for(int i=0;i<x.length;i++){
  162. // res[i][i]=1;
  163. // }
  164. boolean f = true;
  165. if(y==0)
  166. return res;
  167.  
  168. while(y>0){
  169. if((y&1)==1){
  170. if(!f)
  171. res=matmul(res,x,p);
  172. else{
  173. res = x;
  174. f=!f;
  175. }
  176. }
  177.  
  178. y=y>>1;
  179. x=matmul(x,x,p);
  180. }
  181. return res;
  182. }
  183. public static long[][] matmul(long[][] x1,long[][] x2,int p){
  184. int n=x1.length;
  185. int m=x2[0].length;
  186. int o=x2.length;
  187. long[][] res = new long[n][m];
  188. for(int i=0;i<n;i++){
  189. for(int j=0;j<m;j++){
  190. res[i][j]=0;
  191. for(int k=0;k<o;k++){
  192. res[i][j]=(res[i][j]+x1[i][k]*x2[k][j]);
  193. if(res[i][j]>=p)
  194. res[i][j]=res[i][j]%p;
  195.  
  196. }
  197.  
  198. }
  199. }
  200. return res;
  201. }
  202.  
  203.  
  204.  
  205.  
  206.  
  207.  
  208.  
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217.  
  218.  
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225. }
Success #stdin #stdout 0.77s 38032KB
stdin
100 5848 764540669
69 2
26 32
11 36
65 77
97 92
12 61
76 52
50 24
47 75
32 23
12 64
45 32
22 72
53 68
26 53
3 30
62 76
10 77
6 68
1 24
80 69
79 3
33 27
29 84
43 37
55 26
92 55
68 1
92 55
69 39
99 80
61 72
52 86
55 49
11 40
16 48
66 54
56 100
47 61
49 81
90 13
35 37
81 90
38 30
47 47
59 34
100 49
34 37
42 25
75 74
70 8
61 24
63 65
60 61
63 93
54 32
32 14
7 1
3 84
5 6
62 16
33 72
8 37
33 64
22 69
68 72
99 64
82 92
8 9
39 86
87 58
10 44
83 23
74 75
25 76
40 95
4 24
85 79
72 32
93 97
61 16
52 26
72 35
31 71
98 35
71 3
81 59
82 56
6 98
63 21
96 10
57 88
72 70
83 74
82 59
97 75
9 54
55 81
86 21
82 86
74 40
3 90
65 88
6 71
77 32
80 42
98 96
90 70
69 30
45 87
26 82
32 57
48 12
24 77
83 46
44 65
47 77
50 79
63 53
61 25
54 25
33 29
92 9
27 100
97 45
24 85
7 60
32 90
2 4
27 51
31 85
100 87
2 11
43 38
4 82
83 25
73 48
10 33
16 64
18 49
45 16
89 3
28 31
37 51
9 41
44 92
5 87
13 40
50 62
84 30
3 76
56 58
41 37
62 62
54 94
25 31
22 54
86 74
52 45
43 3
6 84
62 31
37 100
59 21
47 16
95 98
54 70
15 15
71 42
78 47
90 63
55 1
76 66
83 30
44 68
53 62
19 37
4 23
38 93
40 41
84 32
41 44
72 15
8 95
70 43
41 53
48 28
15 18
12 85
63 98
36 87
92 70
92 56
62 85
78 42
5 100
70 27
51 37
84 48
96 12
26 92
24 1
100 8
28 69
25 93
37 54
65 100
97 20
84 79
66 12
93 88
42 89
37 85
58 14
69 93
97 14
83 2
23 14
52 29
80 48
59 57
78 24
46 96
70 95
11 91
54 15
5 86
25 36
7 70
12 34
35 2
62 33
51 47
68 42
50 55
14 30
14 9
77 28
61 47
47 7
98 56
29 65
7 65
7 64
35 23
76 38
15 38
16 11
27 95
71 44
18 11
22 58
44 13
34 21
39 64
17 79
29 29
86 22
4 31
18 57
61 85
45 56
12 35
4 16
60 82
56 83
27 27
52 27
57 52
99 52
68 23
17 59
47 91
55 50
49 26
3 31
86 13
84 90
37 60
35 85
37 99
62 93
14 94
1 40
64 72
28 5
32 69
35 63
51 43
17 60
58 17
42 40
25 87
58 61
59 96
13 28
26 31
64 94
96 31
10 18
99 82
46 59
73 41
7 85
16 60
27 59
57 77
33 9
51 1
22 55
93 16
52 4
86 60
77 96
51 96
2 92
1 20
33 57
86 87
39 14
49 38
73 80
67 94
24 54
35 45
2 64
2 3
24 60
74 63
54 96
25 54
98 71
12 66
73 92
73 52
94 59
79 90
54 96
19 12
36 88
90 34
81 49
54 92
26 23
34 47
65 72
43 35
14 52
92 20
98 6
25 22
81 60
21 17
17 2
78 68
71 18
65 23
25 9
47 83
20 33
10 60
91 12
100 90
53 34
40 80
47 8
14 92
36 74
64 78
24 77
19 35
15 47
69 9
70 86
85 29
5 66
40 68
93 22
84 43
34 45
10 13
27 61
48 20
45 71
14 38
22 21
39 65
58 99
17 88
53 72
64 97
36 92
8 52
47 86
9 66
42 13
21 4
91 90
64 7
54 80
71 37
53 91
53 71
83 36
87 75
13 53
66 98
33 91
41 49
91 23
100 39
11 95
89 72
67 50
50 47
15 41
49 49
22 46
38 11
16 84
6 74
21 81
42 46
22 2
69 17
35 31
17 41
88 47
7 47
54 38
56 5
72 18
83 9
97 51
64 56
94 66
83 23
2 40
80 17
33 8
82 90
52 59
66 78
71 30
25 74
73 30
53 61
59 7
38 58
95 85
33 36
25 32
29 89
19 22
44 20
51 84
70 12
51 52
90 64
48 13
20 42
27 16
59 48
28 77
39 78
100 57
79 91
79 41
85 45
60 17
12 16
25 79
45 93
42 7
5 9
85 54
12 22
66 99
17 82
68 28
57 9
54 46
30 52
36 9
50 86
88 54
80 62
17 30
3 70
29 31
66 57
75 47
40 5
22 86
70 91
96 62
50 20
6 85
52 97
24 62
22 61
96 83
97 57
49 72
10 45
2 60
39 30
36 82
10 70
56 39
56 6
8 82
44 11
35 14
54 39
38 97
36 61
94 64
98 66
88 61
74 42
57 72
3 70
41 90
83 8
80 81
33 83
97 32
59 67
36 82
77 40
74 51
82 64
63 47
79 82
32 58
8 7
90 51
39 62
2 29
49 55
79 48
86 33
85 62
3 35
58 73
64 97
20 3
60 11
10 60
2 82
65 84
61 70
2 3
15 28
57 88
100 92
20 62
95 83
87 83
94 42
18 75
92 12
65 95
88 45
16 88
96 89
86 99
31 63
50 64
98 63
87 11
48 57
47 37
94 70
17 28
89 4
9 85
19 99
27 82
43 6
68 27
42 39
1 17
50 12
53 30
15 38
7 8
70 44
18 40
8 8
50 77
78 68
62 99
21 33
43 11
84 28
62 33
86 93
27 99
51 100
17 55
80 11
42 87
71 75
10 12
16 74
94 37
36 95
59 5
56 45
81 51
83 56
27 89
70 19
34 42
41 54
17 51
100 11
74 45
72 82
17 84
61 18
61 66
7 58
58 24
87 15
72 78
87 1
64 82
65 31
45 33
29 36
18 84
86 78
43 32
31 65
16 95
60 58
19 95
29 96
86 23
26 56
21 27
67 46
15 46
65 81
82 46
7 75
83 44
64 6
12 61
5 9
70 68
54 42
60 77
53 10
77 34
76 27
76 21
17 15
66 94
98 59
4 21
4 88
37 55
39 87
24 5
84 39
61 9
54 11
54 74
34 50
44 4
73 42
35 12
79 98
80 99
63 5
59 53
33 37
29 27
2 36
97 88
92 52
47 97
78 16
71 74
27 57
1 84
50 23
84 91
14 87
64 38
100 24
9 88
21 51
50 4
44 36
93 44
77 28
34 11
6 75
80 49
68 92
29 50
48 39
92 80
35 36
17 14
34 98
6 99
75 91
57 78
100 52
57 82
99 22
66 59
18 40
30 58
75 26
49 22
85 93
54 88
70 43
42 61
57 57
100 92
19 39
65 88
9 5
78 95
65 17
20 78
46 31
42 97
17 73
78 20
90 99
57 2
30 87
87 41
68 77
22 39
7 49
100 90
76 36
6 61
90 61
34 64
39 75
30 47
98 37
81 53
79 37
7 63
4 20
9 50
37 45
18 27
86 88
59 74
14 81
43 55
22 6
53 72
87 25
20 56
22 94
20 92
61 98
49 80
66 42
10 70
46 99
7 64
57 54
92 11
53 35
2 8
72 44
37 36
9 17
33 65
35 85
75 54
30 82
1 69
73 60
5 60
61 99
88 42
27 3
82 10
29 21
68 91
60 27
41 84
14 19
100 73
47 98
46 44
61 83
65 31
52 76
68 95
47 77
97 54
88 57
60 12
29 89
47 59
60 21
48 92
2 18
38 56
51 39
98 66
82 65
67 18
1 60
39 19
19 94
23 44
81 36
83 14
14 60
86 41
54 14
38 22
35 14
49 16
68 45
94 45
48 82
9 29
22 98
14 38
31 80
29 45
73 17
64 27
17 85
84 42
21 20
10 51
48 54
64 86
27 35
63 74
18 48
53 40
27 37
18 90
32 76
13 72
49 42
65 82
97 26
32 94
87 83
72 76
46 9
12 98
17 9
2 66
24 83
69 53
23 86
46 1
44 52
96 52
41 30
41 29
41 37
75 11
37 73
9 59
33 90
59 33
70 10
8 13
55 78
59 50
90 82
25 66
13 38
38 83
97 23
47 76
50 76
48 45
75 65
33 89
75 10
19 12
81 69
14 4
55 82
15 22
23 60
5 95
17 75
57 97
11 12
16 86
40 36
60 85
96 42
89 31
15 32
20 96
1 35
43 46
20 96
19 63
33 91
72 96
32 98
85 44
75 20
27 74
95 7
63 60
88 9
66 37
17 61
35 76
37 20
59 60
64 98
36 28
8 76
25 63
33 69
40 21
9 79
52 84
27 88
49 49
5 66
7 48
99 61
55 75
9 28
18 100
36 51
20 94
40 89
82 51
79 68
50 61
99 26
75 74
40 88
17 93
51 89
20 71
43 58
62 12
56 64
69 76
55 50
31 15
51 52
58 5
59 40
30 26
95 36
79 31
21 51
44 69
16 26
62 65
30 35
28 85
10 40
75 6
49 91
19 6
13 92
69 93
18 78
15 34
75 22
36 13
57 35
36 24
57 65
44 65
99 70
74 85
22 94
71 94
74 72
73 35
65 26
18 29
55 73
58 12
42 25
93 37
71 71
46 22
77 71
19 6
16 45
97 93
31 35
71 57
99 85
59 20
88 16
73 29
92 11
99 66
75 38
98 46
89 99
18 49
53 93
79 11
47 71
94 29
71 89
98 7
69 42
86 9
31 14
34 61
53 50
45 60
49 59
85 70
19 26
73 86
58 84
76 15
100 83
22 11
54 82
70 2
19 36
4 42
58 21
48 43
40 4
12 47
1 13
56 98
52 43
18 53
41 42
82 4
33 26
43 81
3 87
59 95
24 86
89 38
28 93
12 100
28 57
1 88
23 43
23 33
13 79
82 93
30 74
1 39
3 18
73 90
23 65
52 96
60 93
72 7
7 86
65 95
18 23
21 98
73 36
15 65
75 9
6 38
95 72
95 27
23 43
62 67
36 57
85 33
17 12
93 26
34 7
71 35
26 86
13 69
61 94
62 45
67 82
74 4
87 39
38 29
63 73
95 63
61 3
31 34
24 26
46 65
64 66
96 16
32 8
90 81
71 9
38 43
73 65
96 93
46 13
66 74
73 57
48 83
81 100
96 3
15 36
10 6
63 78
99 79
14 73
45 9
26 87
6 29
68 82
40 35
23 100
21 26
81 21
25 76
71 61
68 35
96 73
83 67
71 49
44 100
32 36
36 100
65 78
10 59
42 41
7 84
53 27
82 81
20 68
54 80
24 68
13 43
44 22
83 71
14 85
79 23
17 39
22 79
35 47
77 26
47 56
61 21
7 45
84 49
56 99
22 55
33 13
34 87
83 69
2 61
25 4
98 62
82 46
16 91
77 54
42 44
96 64
37 7
62 66
67 96
17 100
11 57
23 76
89 61
88 71
74 86
79 87
7 30
100 31
29 91
97 21
93 40
68 83
27 47
89 73
19 58
8 23
8 47
91 34
96 54
8 51
62 34
88 57
57 56
62 15
25 97
67 46
4 44
4 97
23 92
83 18
74 41
36 30
50 68
21 76
29 100
3 16
45 46
3 59
83 31
100 43
15 1
38 65
84 95
68 78
23 79
56 67
59 56
77 55
81 3
81 84
41 40
29 78
48 67
40 3
77 45
37 94
93 88
40 98
20 75
62 57
22 14
91 99
40 90
44 35
91 70
41 20
73 4
91 5
36 28
22 64
65 11
15 3
11 51
93 49
3 93
4 82
84 54
65 23
31 59
54 71
82 14
27 25
56 14
27 91
25 8
19 94
64 100
93 76
49 35
45 21
25 92
44 72
92 86
47 61
63 63
13 75
84 48
54 31
12 27
79 80
5 79
28 11
57 35
27 44
28 70
30 79
50 56
24 93
54 95
63 40
39 44
70 82
16 8
55 30
13 41
90 98
32 23
47 8
27 21
91 98
50 31
20 51
31 77
61 50
67 86
72 98
34 18
65 40
57 65
44 35
48 92
21 67
100 69
11 81
93 61
40 100
12 65
24 16
7 95
47 90
80 18
91 21
8 8
44 5
84 50
11 11
54 98
17 33
38 70
44 59
60 7
86 67
13 3
33 89
64 1
19 49
36 17
88 12
51 95
18 66
43 60
8 19
58 5
44 21
89 6
18 12
35 66
14 69
72 7
58 24
37 90
36 57
81 79
42 100
82 31
20 60
95 51
11 25
16 2
33 43
86 94
58 15
40 95
21 80
25 63
48 36
53 45
97 62
45 98
90 37
50 14
49 4
97 41
45 54
99 60
14 16
7 100
73 45
86 40
68 26
55 8
32 15
92 67
45 68
71 63
72 79
81 69
89 62
30 64
21 56
92 22
97 14
6 19
38 64
93 80
23 34
51 42
59 17
27 30
65 10
57 37
98 53
97 80
32 70
76 35
79 82
30 84
60 42
69 26
70 35
57 51
11 5
9 58
53 71
35 90
55 9
50 93
47 75
54 96
63 99
71 16
51 11
98 73
99 43
14 49
38 69
34 47
84 15
87 67
31 82
40 25
96 89
74 7
98 86
5 29
65 74
47 54
76 82
33 89
6 71
94 14
89 37
99 76
90 33
72 91
85 24
66 6
65 90
67 63
64 23
83 65
75 67
61 69
42 77
17 33
89 43
31 63
8 75
62 97
9 89
86 21
26 89
89 13
70 14
62 5
22 22
17 38
49 63
94 31
51 61
13 77
37 67
11 12
7 63
43 62
23 50
95 11
67 51
43 95
76 35
28 87
77 86
1 85
66 55
98 10
24 3
48 44
12 91
26 12
13 43
73 20
18 23
14 86
34 71
77 40
68 90
95 18
22 49
12 69
4 17
39 94
63 13
30 6
31 98
82 67
23 66
69 85
75 34
18 89
47 14
67 72
70 2
49 85
96 22
5 43
25 46
40 82
99 97
84 97
49 1
25 84
30 74
94 27
41 6
55 79
9 76
2 46
93 26
62 82
68 46
64 49
5 8
44 97
5 61
86 88
87 51
39 4
22 57
46 90
63 70
71 28
41 38
1 36
66 24
68 11
38 99
71 76
9 1
51 97
85 62
43 27
33 91
53 65
3 98
58 13
38 89
25 94
25 68
63 90
13 73
71 51
77 51
10 67
50 39
38 71
52 53
6 90
2 91
51 96
72 15
25 51
28 81
40 97
95 74
21 22
5 73
47 50
2 30
50 42
5 13
9 50
54 100
61 10
73 14
19 57
92 96
69 74
59 55
62 80
38 13
72 21
33 28
36 96
83 63
33 55
41 17
50 35
50 86
11 16
85 8
38 6
41 14
78 71
65 11
70 8
11 63
8 61
83 65
94 15
56 85
84 64
65 87
22 82
76 21
13 97
72 40
60 98
73 96
5 60
6 35
93 57
7 20
22 82
5 59
2 84
33 54
23 23
96 13
65 74
90 22
71 54
62 43
72 77
42 69
51 36
99 33
88 22
66 69
19 67
96 78
12 87
57 86
71 14
56 1
54 52
87 88
66 45
28 43
25 73
62 33
58 4
100 30
17 35
8 38
48 99
43 19
75 47
92 1
30 86
79 60
11 32
26 29
62 83
28 71
20 55
4 94
10 17
9 19
48 14
1 38
91 74
73 70
91 35
98 12
68 50
25 12
2 58
53 26
21 7
62 65
69 44
8 40
87 90
3 47
92 98
18 50
30 35
22 50
48 12
77 69
95 40
99 28
84 11
40 54
24 78
81 43
82 71
15 20
55 25
48 56
8 2
100 1
42 21
97 33
50 93
72 2
73 72
86 79
11 21
29 4
51 41
90 40
31 62
76 93
54 27
86 28
90 8
55 61
56 71
7 66
51 53
12 70
47 52
63 14
76 71
77 75
63 90
92 62
19 34
56 82
22 71
87 85
81 94
47 7
65 75
58 6
53 79
30 1
48 50
80 79
28 80
28 22
53 91
86 61
18 64
30 55
69 88
89 76
63 55
98 8
84 65
79 98
13 58
65 98
75 47
94 13
69 91
19 5
22 6
43 83
44 65
46 15
9 40
37 68
65 81
98 39
60 83
76 80
77 39
40 30
69 78
95 54
6 36
64 75
20 62
77 30
89 60
50 68
49 36
99 99
35 76
54 87
71 79
21 65
51 62
11 74
49 74
23 52
70 43
14 72
15 66
13 33
97 92
65 81
49 37
62 16
26 61
84 100
74 97
76 72
86 72
82 19
26 35
64 50
11 38
96 22
1 57
11 57
44 25
53 38
73 18
93 69
90 89
45 87
74 19
20 87
42 39
65 78
10 32
100 25
71 72
41 67
11 33
20 54
21 25
28 76
11 12
50 100
24 45
8 34
8 65
38 53
39 98
76 94
77 53
68 5
97 57
66 99
92 49
99 2
43 94
76 23
64 43
76 73
70 77
71 17
38 52
45 4
64 13
4 10
67 77
40 1
26 35
33 94
86 82
80 65
51 9
94 6
37 46
66 97
15 7
42 22
9 60
32 9
75 12
18 46
1 81
53 91
77 63
68 3
57 90
9 60
49 69
44 81
89 89
89 13
77 65
73 86
86 64
4 43
36 82
62 99
4 52
20 90
44 9
61 59
33 86
46 83
65 3
60 24
31 40
90 62
15 63
18 100
1 36
40 27
24 24
76 79
81 16
33 94
16 56
4 46
4 99
30 5
51 60
48 92
91 43
39 89
5 71
9 10
14 80
85 14
34 18
79 61
95 53
90 35
72 10
19 7
39 83
25 62
75 99
36 97
85 73
68 6
3 24
78 56
87 27
22 95
18 30
51 33
40 12
14 34
65 61
79 26
7 23
26 14
41 9
76 31
66 59
85 52
89 29
31 49
24 98
14 41
86 63
60 60
21 85
61 14
52 2
61 43
27 73
25 71
76 15
43 4
81 15
28 62
17 39
5 49
16 28
36 98
4 90
16 88
43 25
93 85
95 81
16 20
98 44
13 97
100 68
74 27
71 21
22 25
93 67
49 30
7 9
53 45
85 69
55 97
5 90
49 9
62 99
38 52
84 85
87 97
54 71
77 96
6 30
40 25
71 65
63 47
34 74
29 26
95 21
8 94
45 73
62 100
52 42
19 24
62 29
50 52
54 98
64 60
13 82
44 55
94 72
57 13
34 63
1 48
12 66
48 22
83 41
18 56
4 24
25 67
23 79
47 87
64 26
73 31
94 13
88 32
23 17
12 92
74 17
20 45
47 9
83 8
81 75
63 58
80 96
80 90
80 43
70 13
49 97
65 69
96 48
75 8
99 58
1 22
79 8
36 23
15 68
50 75
46 28
7 6
99 13
13 90
19 49
23 47
95 51
96 20
75 77
83 36
43 41
13 91
5 84
42 5
18 80
89 10
50 91
99 7
41 69
21 82
1 55
35 26
14 36
69 79
51 54
54 29
16 36
74 89
62 49
72 71
35 32
2 98
3 33
61 98
49 5
90 84
84 38
62 71
39 83
33 30
29 42
71 49
7 67
71 22
33 40
12 21
76 99
54 74
96 86
65 30
78 22
49 58
94 86
5 72
38 20
59 54
57 61
33 86
85 71
66 88
7 39
81 97
71 74
63 30
53 43
81 49
66 6
30 31
44 78
66 2
45 82
34 22
33 28
11 93
50 53
62 3
70 34
59 69
89 18
92 29
68 5
4 75
90 22
53 93
67 31
65 76
74 47
52 19
1 3
4 51
31 37
55 75
62 72
25 11
42 59
64 34
9 5
98 60
90 84
96 79
63 1
87 30
15 2
82 16
12 20
61 48
10 6
84 1
89 72
43 43
20 33
58 18
34 93
97 85
80 31
93 91
77 62
81 31
41 68
98 1
83 49
76 95
22 42
56 17
5 9
52 14
23 37
4 31
97 79
21 9
20 44
51 60
40 78
78 43
18 29
68 29
15 94
17 52
91 19
35 20
67 20
15 70
47 55
75 38
17 84
4 59
40 87
16 52
25 52
40 72
88 27
95 90
55 81
19 16
45 64
16 4
65 23
22 36
52 90
26 32
79 22
17 81
9 25
81 36
41 84
20 6
19 57
43 33
39 96
79 21
48 45
63 100
61 21
64 73
4 68
97 40
35 67
5 8
72 56
18 75
52 24
47 54
80 38
95 42
20 99
41 45
68 75
55 94
67 37
95 51
65 13
47 15
40 40
37 42
54 24
4 62
43 16
86 22
42 70
28 64
61 69
79 2
4 75
3 42
83 19
67 52
25 39
26 57
87 6
55 80
94 44
83 12
54 7
71 86
26 38
73 19
62 38
56 63
62 15
58 67
23 12
70 11
22 76
47 76
11 35
15 22
2 66
5 5
43 90
56 21
84 87
58 95
4 57
68 82
25 81
71 14
48 60
60 20
47 45
10 47
37 51
12 53
14 66
80 22
12 37
44 83
39 76
62 53
16 3
87 33
46 56
89 47
90 80
69 47
79 37
9 21
58 57
84 47
19 41
58 57
98 30
44 58
60 67
5 77
32 9
57 75
90 82
27 84
73 25
31 54
7 73
85 40
57 70
9 70
64 9
80 19
54 69
15 13
63 87
59 40
22 66
17 85
49 98
41 10
39 49
16 40
86 71
62 69
83 82
44 16
15 75
71 77
89 87
47 58
81 96
91 33
69 47
81 59
47 80
18 10
1 96
74 77
14 41
66 78
49 14
27 79
42 40
15 44
70 23
8 95
78 80
19 83
8 41
89 23
14 1
65 25
31 38
77 32
10 26
40 77
23 56
42 27
46 46
14 61
4 88
3 94
79 82
27 76
92 40
72 39
97 12
95 48
42 24
98 95
93 75
63 30
2 34
71 24
7 76
2 59
28 32
36 9
23 22
70 10
16 38
3 38
85 43
56 86
10 54
13 94
66 91
41 42
59 9
56 13
60 18
79 53
33 19
31 7
76 78
44 8
19 80
71 47
83 36
13 60
21 33
90 49
44 72
58 21
8 21
85 43
58 58
14 51
5 83
3 78
7 43
35 10
60 14
70 94
18 32
24 92
55 29
34 18
55 85
7 97
37 6
6 41
34 28
75 42
100 15
25 13
11 42
54 65
74 95
86 24
47 5
88 6
36 35
12 76
68 56
40 91
2 75
41 90
73 88
83 6
22 95
22 78
99 78
32 80
8 98
98 100
68 73
18 99
36 66
100 33
14 74
23 55
18 81
37 89
30 16
34 93
49 49
35 18
82 76
43 69
98 93
9 33
46 25
67 100
11 1
59 59
59 65
42 52
23 65
35 79
9 50
90 57
34 87
68 33
99 62
70 4
53 55
28 5
14 15
14 14
20 14
43 92
90 60
92 34
56 53
59 72
83 77
93 71
41 24
4 13
27 10
85 42
55 73
92 36
23 69
16 77
3 53
61 31
38 64
51 80
36 45
46 83
91 58
87 44
75 48
56 35
90 5
32 28
90 13
53 31
62 66
87 33
10 66
34 4
10 57
34 94
96 80
54 86
37 89
18 2
41 80
91 51
22 73
14 62
8 82
19 5
65 60
57 2
39 75
57 49
78 13
18 32
81 72
69 88
78 41
34 64
45 87
24 43
65 58
85 44
57 57
87 90
3 91
11 33
48 26
21 91
79 6
79 38
61 61
49 30
27 64
16 34
25 64
85 38
65 79
40 36
97 51
40 95
66 29
92 15
91 96
47 18
45 77
46 87
30 93
89 55
94 56
50 46
44 44
69 73
37 6
73 7
92 92
23 19
70 81
24 46
59 81
10 71
54 96
92 57
4 46
98 76
53 96
16 39
29 45
24 46
46 31
28 63
17 92
39 28
99 37
30 55
7 95
31 72
55 9
53 20
11 34
60 60
61 45
61 69
71 25
83 5
67 30
56 10
7 8
96 83
15 82
32 46
38 99
8 85
55 66
100 54
31 5
84 72
11 23
78 15
32 59
31 44
68 63
18 2
70 69
41 56
60 48
89 42
28 68
53 97
34 81
17 84
5 6
70 65
69 72
25 38
57 29
84 69
78 36
56 9
33 43
79 80
87 54
94 99
10 76
82 85
70 16
1 36
22 85
84 81
76 94
34 61
4 40
57 91
100 45
72 20
10 48
90 51
79 89
100 85
4 33
69 89
48 23
36 78
23 44
100 24
32 3
60 22
70 58
10 51
37 52
66 14
100 55
14 36
100 91
77 19
95 79
7 88
16 85
39 8
55 28
68 67
3 67
36 58
35 73
71 93
37 12
7 35
38 22
11 42
47 14
95 55
69 35
38 42
88 100
84 33
69 9
44 52
26 59
43 7
10 94
20 62
45 94
50 38
92 91
63 27
56 98
68 37
94 44
85 40
92 43
62 15
5 95
92 54
93 13
25 34
31 13
32 29
61 62
40 20
75 88
94 55
34 71
82 2
37 42
12 31
41 39
64 99
32 24
76 44
51 5
35 59
54 14
30 84
23 84
2 5
3 44
34 90
70 16
46 37
66 57
43 96
99 40
39 20
68 48
62 24
70 8
69 23
12 10
74 94
37 13
52 40
60 11
3 30
24 26
30 88
91 20
61 40
2 37
41 38
71 83
23 36
70 58
71 35
13 89
17 93
49 33
45 10
17 33
69 99
13 65
46 93
90 22
30 30
15 39
55 78
90 35
55 65
2 78
73 87
21 40
65 11
67 9
21 90
15 53
83 12
10 56
6 31
26 31
86 42
88 7
23 86
13 85
37 67
43 85
45 80
46 88
24 77
77 68
4 32
78 63
32 55
3 93
78 53
1 44
95 96
66 41
71 66
26 39
71 79
69 99
7 39
48 90
7 31
15 50
61 18
54 47
75 71
20 32
25 62
29 2
49 4
60 1
44 43
51 48
33 60
81 11
14 29
61 52
85 72
31 100
25 71
35 1
37 72
25 28
40 25
28 49
63 34
52 60
30 83
92 72
58 26
9 19
97 4
60 45
77 73
15 91
37 32
51 3
93 30
66 14
17 19
83 8
22 13
99 93
15 53
81 67
8 76
4 26
87 51
79 18
64 25
6 83
86 4
39 58
22 24
64 76
81 25
93 95
48 48
23 49
52 78
96 99
26 87
3 42
56 89
71 98
52 53
63 84
23 7
5 19
4 65
12 33
3 17
5 37
45 6
95 52
78 68
58 49
9 23
19 90
42 62
99 66
20 69
96 86
94 49
84 23
91 90
63 33
15 16
39 46
75 90
45 93
54 97
36 74
31 59
56 14
72 22
37 55
26 14
57 66
66 71
36 6
79 36
77 70
65 80
97 79
97 34
71 79
59 87
13 57
70 67
100 15
11 55
34 81
19 49
77 26
38 34
48 23
2 21
86 91
95 63
17 51
64 15
17 73
24 72
87 17
84 37
86 10
61 63
87 4
77 41
17 18
63 80
22 84
85 4
84 29
86 12
94 70
35 21
56 82
21 5
55 93
23 15
77 24
19 40
99 85
18 8
15 60
46 44
33 20
69 91
7 53
3 54
6 89
92 80
57 1
14 67
13 90
46 14
39 17
77 61
13 46
35 48
33 39
57 15
27 30
99 69
22 56
67 36
53 43
99 86
6 19
12 49
47 95
88 48
54 60
89 87
72 94
99 72
47 100
59 67
51 55
82 18
54 82
87 49
50 20
31 72
35 72
74 4
14 78
41 68
54 28
58 96
87 62
67 22
63 77
67 28
20 82
14 33
20 61
19 13
25 45
35 31
35 1
75 87
70 99
89 46
67 10
70 51
79 33
100 3
72 4
36 37
24 92
39 11
35 60
6 40
74 48
29 28
11 75
92 95
37 21
18 31
4 62
61 32
41 33
48 20
12 42
41 95
90 73
34 85
7 66
37 13
28 84
60 68
12 90
24 26
74 29
49 100
26 36
18 21
7 59
54 43
24 6
19 87
74 31
36 28
96 43
42 74
19 59
100 81
72 29
93 36
49 43
10 1
54 96
33 4
13 79
28 56
56 95
95 33
95 49
56 41
39 41
54 92
70 83
54 48
66 77
42 64
9 49
67 13
20 25
99 51
8 35
74 51
95 98
51 19
83 8
31 96
70 54
2 6
95 22
59 30
8 36
12 47
72 3
10 36
75 96
86 90
34 45
46 85
14 94
96 51
4 70
77 13
50 10
88 93
48 50
23 97
82 82
65 60
57 68
79 48
40 26
51 1
11 99
89 2
35 79
33 69
37 49
15 65
73 84
72 82
42 87
52 68
98 29
1 93
18 99
77 5
40 62
64 95
36 47
46 81
56 29
46 47
31 33
54 24
91 35
50 8
84 76
50 23
27 74
97 5
19 89
75 84
35 67
25 15
72 21
92 34
42 2
4 22
100 78
63 60
15 88
44 71
21 95
68 53
66 96
100 11
89 5
7 39
93 26
21 64
26 47
6 59
92 10
64 29
100 27
89 73
73 9
48 37
8 3
20 91
16 47
100 55
61 19
51 19
96 34
63 38
91 42
83 28
6 66
39 81
56 33
78 26
1 54
10 5
77 92
92 1
7 33
62 72
65 83
77 33
60 67
23 19
12 32
99 48
43 56
26 39
56 62
62 65
58 40
99 7
71 6
69 60
22 97
49 69
95 47
10 26
69 72
87 78
16 22
53 99
48 85
91 94
2 59
71 3
76 28
13 90
56 13
50 36
12 50
29 86
76 97
10 2
7 6
100 47
48 44
49 48
11 19
13 81
73 4
69 1
30 12
61 35
36 34
18 89
82 76
80 88
39 100
34 51
47 34
58 74
54 50
12 95
70 78
19 23
80 12
62 62
49 65
41 41
14 43
23 29
58 85
52 66
13 83
38 73
42 56
32 15
48 12
67 25
39 15
22 7
59 43
27 30
46 79
20 50
35 83
56 57
49 9
46 59
50 83
99 24
57 38
100 6
1 24
4 55
28 91
14 25
88 98
37 45
59 56
25 78
22 74
36 26
3 23
19 85
99 25
19 64
8 44
95 20
85 33
65 97
60 100
47 24
82 2
24 44
25 27
30 35
63 82
16 93
100 46
64 88
6 22
63 59
89 79
11 27
15 22
86 72
56 98
15 20
48 74
60 20
20 59
65 24
12 17
35 98
3 85
39 82
27 74
25 56
57 8
36 5
69 14
54 51
90 85
84 94
73 50
81 19
30 64
70 64
42 77
81 61
88 93
69 41
45 62
18 47
21 23
78 85
41 12
76 21
41 66
62 20
47 59
14 87
98 68
48 60
68 92
9 36
76 41
48 43
88 39
50 24
3 88
1 53
28 62
72 6
37 64
69 51
5 89
48 30
89 87
6 19
77 80
73 3
6 66
9 97
41 79
79 10
96 32
2 63
88 10
31 1
56 71
65 27
52 47
60 25
43 83
98 85
76 70
19 63
4 89
67 94
59 27
47 11
8 23
86 72
35 93
35 100
50 32
39 89
75 67
21 90
84 33
20 52
30 25
55 46
16 67
35 76
18 65
2 94
66 90
1 15
25 100
89 48
67 71
75 55
23 9
8 89
68 48
9 26
42 14
87 20
60 92
93 7
88 15
7 46
64 53
54 28
94 48
49 34
70 81
69 37
35 28
9 79
93 32
80 28
78 99
45 41
9 97
85 42
63 78
69 27
79 53
53 31
16 57
94 34
87 92
2 63
85 65
9 90
63 81
95 20
27 7
57 10
28 15
38 88
55 30
86 78
100 36
63 25
69 32
99 73
56 71
60 20
44 27
29 7
94 12
80 97
53 17
8 10
40 44
76 1
57 30
56 40
92 16
31 1
78 19
96 30
10 97
99 90
45 44
88 59
20 82
3 77
75 56
52 15
53 54
10 25
14 32
36 39
81 42
83 90
67 27
97 48
45 26
12 13
36 78
41 38
55 77
95 10
96 27
99 86
35 82
95 36
37 42
100 68
90 1
56 30
38 37
21 72
81 22
66 77
9 19
87 46
100 88
76 61
3 90
85 60
98 80
82 85
27 46
99 65
71 46
22 28
39 27
57 41
82 66
79 98
56 70
47 12
64 3
59 82
28 41
23 64
83 51
58 64
15 72
43 38
80 96
93 31
44 69
84 49
79 4
85 6
60 86
64 62
75 61
61 6
56 7
32 48
83 10
72 53
62 41
70 82
66 62
24 6
78 77
24 87
1 21
21 71
77 17
16 21
87 13
30 18
3 99
5 55
93 97
94 4
16 32
72 8
43 33
23 33
28 75
23 83
11 64
78 39
12 3
97 65
9 94
7 36
96 62
40 29
61 61
2 18
61 37
84 90
40 45
68 54
21 80
68 53
30 2
34 55
78 15
7 79
48 55
81 6
90 1
15 71
58 12
62 45
98 47
76 53
22 34
86 7
33 33
99 18
92 58
73 13
47 87
63 54
98 54
47 3
40 61
89 37
64 70
29 90
66 84
27 99
26 23
30 28
62 59
42 84
36 12
2 23
39 6
65 42
51 13
61 62
35 67
80 99
16 75
18 19
63 73
37 37
13 74
60 93
24 34
49 56
96 77
43 7
10 40
35 8
25 25
46 54
2 79
52 29
48 43
94 17
20 42
10 84
63 73
87 90
97 43
81 2
8 98
11 96
20 73
36 35
88 42
44 25
21 51
83 76
8 87
26 57
15 46
98 40
29 95
60 6
83 46
31 40
95 29
95 88
13 84
65 69
8 2
97 92
66 9
84 24
15 20
76 75
15 84
13 49
89 81
4 85
28 29
68 89
96 14
82 3
24 86
79 49
65 97
80 20
71 27
60 13
27 31
76 29
86 52
61 76
16 63
9 42
40 92
44 54
41 27
82 90
2 13
96 91
77 15
96 15
24 58
19 78
47 84
40 15
99 99
49 8
96 100
43 39
3 92
1 29
40 85
21 98
34 9
27 74
81 37
19 44
31 58
52 48
59 7
96 26
4 38
45 23
76 74
81 30
70 21
51 19
74 32
69 23
19 29
34 75
26 15
86 33
15 84
17 43
64 82
92 21
55 95
12 9
85 60
58 41
66 58
67 63
73 60
70 9
1 74
2 79
17 30
97 53
49 80
95 39
35 13
93 34
9 90
33 57
25 93
60 59
10 99
82 47
75 17
100 37
82 38
66 100
92 34
5 74
47 19
70 11
71 47
95 48
99 52
61 26
53 38
68 22
94 36
25 42
9 82
58 82
16 15
29 20
71 55
23 65
51 20
58 63
95 79
84 87
40 18
98 34
73 44
96 37
30 42
54 73
98 55
75 89
18 35
81 54
93 95
56 6
23 26
95 89
95 75
63 55
36 37
57 24
35 17
72 13
75 42
58 2
13 70
7 21
47 42
55 75
74 60
63 32
34 2
2 76
98 38
29 11
74 71
14 71
22 29
10 30
91 43
23 39
58 55
71 68
36 21
24 61
68 8
85 23
17 46
69 63
11 95
29 50
64 27
58 86
23 50
57 1
95 83
85 35
37 79
43 99
51 26
30 12
97 17
8 53
26 81
8 55
77 88
74 13
2 34
80 17
49 73
87 67
84 68
66 28
82 13
49 19
18 100
84 37
13 30
1 90
97 40
22 12
40 12
84 3
95 7
61 27
39 27
50 31
70 26
98 70
17 35
42 100
76 98
97 6
40 2
16 83
70 48
47 98
77 99
64 17
98 76
94 45
94 35
15 20
82 40
79 19
57 41
82 89
24 52
3 7
97 54
58 48
92 10
93 37
24 39
82 3
80 57
46 100
27 43
85 59
85 21
13 94
54 38
57 60
52 22
14 73
55 80
22 14
30 16
84 17
61 30
61 10
81 30
46 100
93 41
40 66
19 94
21 90
59 29
51 97
65 95
11 45
74 25
16 13
25 64
81 43
88 36
30 86
45 96
92 52
70 16
61 84
36 45
98 43
15 90
14 8
81 60
30 14
76 28
13 31
4 1
40 14
56 82
95 99
92 16
64 16
29 16
100 28
96 3
36 61
10 68
38 85
18 40
96 23
50 75
11 97
70 25
4 12
14 53
40 63
63 75
83 66
48 38
96 75
48 89
29 83
66 46
25 43
26 26
75 6
92 61
42 16
9 65
56 59
73 11
11 34
69 66
16 40
85 38
28 6
77 16
71 56
77 30
25 85
38 17
85 39
67 37
9 87
24 84
15 6
27 9
36 58
19 64
76 26
65 76
65 60
80 17
28 48
16 55
67 21
70 100
11 51
83 71
13 24
85 89
93 63
7 91
88 99
12 29
13 42
96 5
29 57
89 39
72 56
9 52
90 61
60 27
83 54
33 88
79 2
34 89
60 92
64 96
14 7
24 6
29 33
92 24
30 92
79 9
98 62
55 64
64 27
28 23
8 19
36 9
55 45
71 74
42 39
18 98
81 38
85 94
70 56
13 45
30 75
60 61
43 32
5 38
47 69
72 93
75 54
41 94
2 7
11 55
22 32
41 59
71 59
63 64
92 96
1 99
28 77
54 63
95 72
22 51
20 58
4 92
72 13
17 46
75 40
44 24
39 95
8 9
96 77
10 41
38 54
73 67
90 74
29 33
17 74
75 5
40 91
1 31
97 14
50 1
21 16
18 22
29 88
84 40
85 84
54 58
47 38
47 38
77 84
67 100
50 72
53 76
29 44
44 37
20 58
42 18
69 64
4 5
95 77
41 73
27 21
8 13
64 45
74 95
67 41
84 50
29 2
12 68
23 2
90 76
71 14
8 9
27 31
67 98
74 78
22 95
75 90
14 37
77 16
96 13
43 4
56 68
4 70
6 29
48 55
41 77
64 31
22 68
19 13
45 2
72 88
49 98
99 86
59 55
82 42
97 74
57 41
39 9
34 96
71 72
22 47
74 40
48 84
38 56
45 72
4 24
55 62
86 53
91 90
97 88
87 37
63 66
1 34
27 23
12 99
18 3
47 20
8 40
31 93
64 40
40 79
98 84
8 2
42 75
13 53
87 97
21 26
18 17
43 92
29 95
9 67
70 74
40 27
82 12
28 1
19 39
29 37
57 26
46 47
98 21
56 82
18 58
10 74
38 34
68 68
90 69
5 97
39 75
35 64
5 20
43 96
67 24
28 93
61 47
56 43
60 89
12 80
18 42
82 67
95 2
16 80
69 43
20 2
89 99
56 77
73 61
3 76
49 62
27 65
40 60
24 21
13 29
42 14
52 69
98 54
29 58
39 58
82 73
53 72
14 56
42 35
45 32
84 80
17 97
78 70
11 10
3 80
21 91
38 11
86 26
27 51
18 97
63 93
81 23
43 19
86 94
57 64
59 77
38 88
37 23
69 47
22 31
90 74
53 57
61 99
71 97
18 10
30 78
3 72
34 67
54 16
47 68
77 85
60 94
14 95
42 8
85 60
68 76
74 72
65 13
79 32
93 22
72 19
77 66
2 30
54 5
91 83
35 85
36 85
21 50
10 42
47 77
92 77
93 79
11 72
58 68
45 36
41 42
74 96
70 27
21 2
11 4
96 56
87 14
14 97
56 46
16 43
66 30
79 28
87 82
67 95
53 79
22 39
59 59
61 27
56 40
98 69
77 67
40 8
61 79
47 16
50 19
38 6
24 41
96 20
15 79
66 42
77 73
72 10
77 71
69 67
70 2
75 72
48 69
83 35
62 66
36 3
68 87
23 8
94 82
31 6
38 87
53 4
31 86
66 63
46 48
54 46
60 39
38 86
26 96
51 30
24 30
22 60
47 55
68 19
94 25
16 6
48 90
24 82
90 73
78 74
53 38
37 53
70 86
57 97
56 31
40 52
31 84
19 11
62 2
86 34
59 12
98 64
73 4
23 36
58 99
76 27
65 19
17 15
69 14
53 72
71 67
60 77
93 79
33 57
13 4
55 49
93 75
53 65
61 24
37 51
81 97
75 88
6 19
4 32
89 61
66 6
25 77
53 26
68 27
29 61
47 7
56 31
90 59
77 15
22 20
5 88
96 84
25 89
34 43
27 70
54 50
93 55
64 4
83 65
91 71
94 15
81 45
82 26
93 67
96 98
31 38
45 94
92 18
26 73
13 50
14 44
40 50
47 20
91 55
100 73
25 99
2 60
71 13
24 8
35 8
71 64
26 19
82 26
9 12
91 76
58 43
37 64
25 43
83 2
11 22
9 80
21 45
87 45
2 26
31 53
9 27
44 79
36 69
40 86
46 47
59 60
46 52
40 67
97 53
7 88
61 68
48 48
23 8
61 62
95 99
75 67
30 77
36 65
17 88
51 17
81 13
72 52
55 79
73 87
66 67
72 31
95 27
45 34
32 14
9 34
75 40
26 19
17 66
70 84
7 55
37 34
16 25
36 91
42 89
86 78
4 16
17 39
30 90
81 51
88 23
11 64
1 31
43 92
10 78
87 18
24 65
29 54
24 81
41 68
8 18
15 95
96 32
41 29
56 96
17 69
44 83
1 89
18 46
93 58
30 86
69 20
11 79
88 45
64 31
87 93
8 64
17 15
84 13
3 82
4 6
59 15
28 5
42 32
39 52
6 41
9 48
57 24
25 66
34 95
59 9
96 88
33 5
42 62
46 2
11 45
76 73
41 18
6 29
50 56
63 30
96 24
46 44
92 7
10 11
69 29
37 76
89 29
42 5
42 95
75 83
17 71
9 100
1 81
7 67
59 18
17 82
88 84
14 38
28 48
48 70
54 2
9 9
57 50
2 14
20 38
99 72
73 32
47 29
38 31
10 29
89 77
13 15
14 9
73 10
48 48
11 39
21 78
53 24
65 73
17 38
18 53
94 64
26 82
21 32
36 56
43 36
92 48
44 13
42 75
60 15
36 74
37 62
46 96
35 84
58 73
25 87
40 92
10 98
72 93
2 21
87 87
95 9
2 61
68 76
85 64
11 8
63 10
44 73
74 36
54 41
55 37
30 80
15 23
95 27
90 14
26 28
86 21
10 13
60 72
24 36
70 67
49 21
87 72
42 73
26 75
50 78
63 20
37 37
9 9
62 1
34 14
8 38
39 18
19 99
60 18
96 8
80 56
69 94
48 67
2 75
68 51
42 83
70 39
17 3
15 32
42 56
66 41
15 94
38 92
45 79
96 49
62 83
95 36
91 81
65 83
76 43
34 51
27 80
25 41
87 94
8 49
30 86
9 43
48 30
80 71
94 86
4 31
6 49
20 16
86 35
92 8
32 12
46 28
100 42
44 49
34 47
89 88
65 21
57 83
6 3
64 82
71 68
42 35
61 53
96 92
84 19
52 76
9 17
65 81
67 3
24 14
21 57
59 72
41 20
3 22
24 65
81 29
31 83
43 43
70 21
35 69
7 61
49 69
40 87
73 33
54 84
10 13
62 21
84 45
72 1
26 39
94 54
45 11
58 85
40 62
22 69
54 60
83 92
28 28
20 26
81 11
38 26
61 19
29 34
83 73
26 20
98 59
56 16
47 66
64 42
88 18
3 45
7 80
78 41
87 86
57 65
41 4
13 72
94 65
59 72
68 49
36 31
16 66
85 24
5 34
96 6
17 11
48 30
96 51
13 84
7 52
83 76
39 8
25 66
63 34
56 73
63 84
32 20
67 78
55 52
27 17
2 18
70 91
4 58
91 10
24 93
81 91
4 49
35 73
18 92
100 29
88 57
9 9
54 50
49 35
87 35
22 52
66 47
86 39
38 62
17 76
94 83
73 91
93 87
56 61
41 96
92 6
43 77
18 37
17 74
68 92
28 27
50 1
59 42
52 6
55 40
80 17
30 92
58 72
30 47
88 82
20 33
15 100
11 36
11 67
3 37
69 4
69 61
88 93
74 69
17 93
24 93
69 9
33 75
16 18
66 39
81 84
65 4
78 36
94 97
3 85
95 90
32 58
89 43
73 28
99 14
71 75
46 69
94 24
63 52
9 10
70 6
72 27
49 57
55 10
81 69
4 98
6 83
74 50
52 53
84 63
17 40
90 72
39 18
38 70
62 8
99 25
62 65
61 35
89 88
80 72
96 84
53 62
30 40
48 63
68 73
43 67
74 85
2 96
46 60
29 78
27 17
57 53
46 58
27 30
61 1
79 93
70 51
5 49
94 3
27 58
14 86
23 47
41 54
38 94
44 59
65 9
36 48
29 87
95 72
34 87
78 6
69 92
13 15
91 86
3 35
19 15
24 81
6 90
3 100
81 79
95 20
100 13
79 74
5 29
64 5
3 39
83 22
56 31
96 56
43 25
45 52
64 94
69 80
76 37
63 30
17 28
83 30
2 18
60 15
56 84
82 14
87 69
61 71
77 15
42 49
11 62
85 86
73 76
9 60
8 1
47 91
1 40
9 8
3 8
8 96
44 49
27 4
66 18
9 92
32 14
88 47
65 80
71 7
40 42
54 10
9 75
68 69
47 38
32 46
83 50
44 55
49 58
76 46
85 26
19 5
28 80
16 32
29 74
33 6
52 47
79 11
22 85
93 4
19 55
35 60
30 41
59 75
25 28
2 31
1 32
58 52
22 10
11 9
44 3
33 57
1 55
84 86
28 81
43 27
27 17
70 79
68 91
22 65
93 20
17 76
4 37
69 42
75 55
92 35
52 59
95 8
1 31
24 1
44 56
5 25
66 20
81 74
48 45
65 87
38 27
5 62
2 33
10 18
68 85
19 17
90 91
23 54
96 7
13 6
23 42
58 40
35 50
61 12
16 69
78 51
20 62
41 13
62 4
70 16
71 79
12 81
13 81
20 34
52 43
90 64
16 44
48 40
89 44
20 22
97 78
41 73
25 82
66 19
5 20
30 42
32 71
48 73
42 50
68 21
58 35
38 7
68 17
53 13
83 73
30 98
88 92
23 57
29 14
23 68
28 3
7 57
91 44
52 29
11 34
11 44
81 33
81 78
71 45
11 6
46 20
31 59
86 37
14 100
63 44
76 68
33 94
71 33
55 19
41 92
47 70
4 22
26 98
57 47
88 63
13 98
92 12
77 26
43 15
39 41
38 58
79 48
71 50
92 23
41 66
43 84
37 100
92 29
85 88
36 61
42 80
60 87
65 8
61 70
11 46
10 45
89 32
28 91
68 67
70 70
55 61
50 50
15 6
12 17
41 8
16 93
58 26
30 3
83 25
87 16
54 99
79 10
57 5
22 6
12 12
12 70
16 88
45 4
27 24
28 89
51 1
94 65
64 77
2 23
52 88
5 71
59 84
20 20
76 67
18 49
72 25
96 85
25 15
21 93
40 73
35 97
80 82
61 81
21 64
51 10
13 47
98 40
63 17
53 75
13 41
34 30
65 28
44 54
77 9
80 21
80 72
53 85
89 66
16 33
32 67
60 49
5 92
45 20
32 74
71 92
47 76
58 67
57 48
100 39
44 25
18 27
47 3
63 42
7 67
73 47
61 68
44 3
17 98
52 70
28 79
19 42
55 4
51 77
85 81
43 62
10 93
20 80
11 4
59 10
53 67
16 44
17 12
59 30
62 71
74 18
86 5
8 65
44 54
35 69
43 57
79 56
24 82
50 40
64 35
80 82
1 30
27 14
93 52
62 67
47 95
63 42
100 7
57 67
24 20
15 54
41 48
45 4
28 57
3 19
5 64
4 75
24 88
26 49
60 7
85 65
67 49
64 58
4 35
76 42
85 10
50 9
50 55
87 73
61 79
35 70
21 67
71 22
79 34
84 80
14 11
20 19
21 36
73 21
77 86
60 64
40 59
86 10
80 21
13 35
54 47
25 41
93 6
17 14
14 92
31 35
80 59
35 49
72 53
61 39
3 61
30 51
10 54
10 84
18 57
79 72
9 56
2 95
38 68
67 69
29 44
51 34
58 31
33 44
32 68
47 82
47 2
4 59
100 49
97 28
82 81
13 36
56 60
91 75
1 56
64 45
46 62
18 78
10 16
46 99
50 68
78 8
52 79
40 4
23 50
33 19
55 21
94 1
99 32
42 46
47 50
87 10
53 34
67 15
72 15
92 73
14 75
23 13
94 43
62 22
34 85
47 42
80 54
52 42
13 25
50 65
74 7
62 53
9 96
7 28
79 72
76 92
79 85
73 39
94 88
81 3
39 10
73 88
15 94
93 91
43 19
20 15
86 53
9 68
50 61
52 81
11 38
49 59
92 43
70 41
48 20
65 44
34 84
24 91
36 77
86 37
19 30
63 50
94 27
42 2
5 85
73 14
34 100
9 34
8 39
50 100
49 67
60 19
32 72
90 28
90 19
18 4
57 6
30 99
69 68
16 54
77 70
47 29
47 96
38 11
44 15
80 51
92 55
45 50
47 22
99 41
81 79
53 30
8 58
88 24
92 88
16 7
5 13
30 66
78 46
46 52
64 7
32 93
69 74
49 44
40 1
5 91
53 27
13 86
41 35
48 96
49 22
52 76
10 25
32 14
4 17
80 15
27 87
93 20
98 37
86 100
96 61
61 79
10 57
27 81
58 7
35 27
52 51
89 31
61 3
38 4
99 92
11 23
22 95
61 41
14 80
64 41
82 52
21 24
91 11
81 29
97 97
55 75
28 51
42 25
2 51
45 21
62 7
96 94
72 37
74 71
76 23
5 80
96 53
55 91
37 16
40 2
76 86
7 91
16 35
79 99
14 78
3 51
21 95
4 19
57 90
40 69
30 39
10 17
67 57
77 17
8 59
54 6
98 96
37 90
49 39
65 9
87 59
11 34
60 52
64 41
4 61
19 42
74 52
64 52
34 84
83 46
7 38
18 18
88 65
78 34
70 54
52 22
63 46
81 42
70 9
1 1
16 32
8 99
68 98
62 70
56 75
20 80
8 94
18 24
23 73
35 44
20 60
33 28
37 71
92 15
43 99
80 47
52 13
20 91
59 84
7 28
2 91
24 70
6 42
89 98
54 33
67 16
54 42
86 74
50 100
56 18
91 2
69 61
19 9
92 68
86 31
34 95
22 64
97 67
40 98
17 11
20 89
6 38
26 50
48 24
61 39
49 68
14 63
16 66
63 15
34 76
89 97
1 92
3 75
76 10
82 3
45 52
18 44
49 40
81 60
44 86
15 21
86 73
5 6
54 90
88 81
45 92
96 75
65 48
2 32
24 39
37 63
99 74
90 67
63 5
15 82
83 39
5 50
99 76
78 89
90 20
42 41
46 75
68 24
95 75
11 97
61 10
93 55
6 35
46 91
1 8
19 81
26 38
17 30
48 74
95 78
83 13
34 33
91 97
87 54
50 53
38 81
15 8
99 37
27 49
86 94
42 45
38 43
94 66
97 59
42 16
79 95
80 43
34 40
26 25
49 98
82 68
15 88
22 54
4 43
6 54
6 16
100 44
22 68
95 26
56 47
89 93
49 43
88 5
65 84
17 100
95 29
19 66
27 91
42 41
43 77
81 61
52 66
56 85
99 100
68 30
64 74
74 60
62 98
32 43
55 65
76 58
21 46
86 53
26 15
24 35
26 57
60 85
70 28
16 70
21 9
31 47
41 70
16 36
19 64
23 77
68 78
4 61
72 58
2 56
80 68
52 68
61 64
68 3
41 74
9 52
8 41
89 69
65 19
12 46
13 49
52 44
95 44
19 86
99 93
72 80
68 11
80 51
77 20
94 90
21 34
15 72
57 72
19 64
39 34
64 68
46 75
94 27
89 93
78 67
4 65
76 96
45 54
80 18
67 34
58 34
9 22
73 34
37 60
81 78
2 57
91 31
51 90
43 31
41 20
82 8
99 73
35 37
9 11
49 86
37 76
59 15
100 65
63 67
82 96
23 73
100 27
82 59
19 54
52 31
95 15
84 14
31 45
51 18
79 92
80 91
94 37
22 45
19 69
79 54
98 1
68 44
61 77
28 56
5 80
89 79
15 21
41 75
52 46
71 28
58 1
26 81
46 8
16 99
22 4
81 57
98 75
89 1
39 66
88 26
53 98
22 98
94 33
8 32
36 8
3 61
12 47
64 58
26 13
49 42
92 27
29 63
82 25
82 37
78 100
31 12
82 17
80 55
16 89
27 25
58 3
88 98
51 67
1 92
29 32
22 52
25 26
52 89
36 82
54 32
97 89
58 86
65 60
59 55
99 47
94 89
61 71
3 18
55 47
78 16
22 41
77 63
75 42
10 68
9 22
66 94
84 98
94 80
70 3
13 28
6 63
37 96
23 38
77 98
1 59
4 71
89 87
40 49
13 77
18 1
23 72
60 53
4 95
41 43
5 52
1 28
55 77
5 24
65 74
37 29
51 45
62 25
60 20
42 15
15 50
38 27
90 74
16 80
93 62
29 21
91 14
42 50
30 53
76 92
19 69
53 85
51 8
59 34
41 31
67 66
5 54
8 19
88 70
73 92
41 80
37 26
56 89
77 82
9 18
55 91
84 7
13 17
90 47
24 16
8 6
35 82
55 72
89 64
6 81
60 92
89 49
50 15
33 30
51 9
95 91
66 3
41 33
58 40
80 5
96 18
59 87
21 91
57 80
25 24
56 72
12 92
68 100
43 47
15 10
81 44
50 80
91 21
71 30
1 87
stdout
621384085