Skip to content

Instantly share code, notes, and snippets.

@ignacy

ignacy/raytracer.lisp

Created July 10, 2017 06:02
Show Gist options
  • Save ignacy/fd6f27bbaf2c583b496517bcfc1b9d12 to your computer and use it in GitHub Desktop.
Save ignacy/fd6f27bbaf2c583b496517bcfc1b9d12 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
raytracer.lisp
;;;; raytracer.lisp
(in-package #:raytracer)
(defun sq (x) (* x x))
(defun mag (x y z)
(sqrt (+ (sq x) (sq y) (sq z))))
(defun unit-vector (x y z)
(let ((d (mag x y z)))
(values (/ x d) (/ y d) (/ z d))))
(defstruct (point (:conc-name nil))
x y z)
(defun distance (p1 p2)
(mag (- (x p1) (x p2))
(- (y p1) (y p2))
(- (z p1) (z p2))))
(defun minroot (a b c)
(if (zerop a)
(/ (- c) b)
(let ((disc (- (sq b) (* 4 a c))))
(unless (minusp disc)
(let ((discrt (sqrt disc)))
(min (/ (+ (- b) discrt) (* 2 a))
(/ (- (- b) discrt) (* 2 a))))))))
(defstruct surface color)
(defparameter *world* nil)
(defconstant eye (make-point :x 0 :y 0 :z 200))
(defun tracer (pathname &optional (res 1))
(with-open-file (p pathname :direction :output)
(format p "P2 ~A ~A 255" (* res 100) (* res 100))
(let ((inc (/ res)))
(do ((y -50 (+ y inc)))
((< (- 50 y) inc))
(do ((x -50 (+ x inc)))
((< (- 50 x) inc))
(print (color-at x y) p))))))
(defun color-at (x y)
(multiple-value-bind (xr yr zr)
(unit-vector (- x (x eye))
(- y (y eye))
(- 0 (z eye)))
(round (* (sendray eye xr yr zr) 255))))
(defun sendray (pt xr yr zr)
(multiple-value-bind (s int) (first-hit pt xr yr zr)
(if s
(* (lambert s int xr yr zr)
(surface-color s))
0)))
(defun first-hit (pt xr yr zr)
(let (surface hit dist)
(dolist (s *world*)
(let ((h (intersect s pt xr yr zr)))
(when h
(let ((d (distance h pt)))
(when (or (null dist) (< d dist))
(setf surface s hit h dist d))))))
(values surface hit)))
(defun lambert (s int xr yr zr)
(multiple-value-bind (xn yn zn) (normal s int)
(max 0 (+ (* xr xn) (* yr yn) (* zr zn)))))
(defstruct (sphere (:include surface))
radius center)
(defun defsphere (x y z r c)
(let ((s (make-sphere
:radius r
:center (make-point :x x :y y :z z)
:color c)))
(push s *world*)
s))
(defun intersect (s pt xr yr zr)
(funcall (typecase s (sphere #'sphere-intersect))
s pt xr yr zr))
(defun sphere-intersect (s pt xr yr zr)
(let* ((c (sphere-center s))
(n (minroot (+ (sq xr) (sq yr) (sq zr))
(* 2 (+ (* (- (x pt) (x c)) xr)
(* (- (y pt) (y c)) yr)
(* (- (z pt) (z c)) zr)))
(+ (sq (- (x pt) (x c)))
(sq (- (y pt) (y c)))
(sq (- (z pt) (z c)))
(- (sq (sphere-radius s)))))))
(if n
(make-point :x (+ (x pt) (* n xr))
:y (+ (y pt) (* n yr))
:z (+ (z pt) (* n zr))))))
(defun normal (s pt)
(funcall (typecase s (sphere #'sphere-normal))
s pt))
(defun sphere-normal (s pt)
(let ((c (sphere-center s)))
(unit-vector (- (x c) (x pt))
(- (y c) (y pt))
(- (z c) (z pt)))))
(defun ray-test (&optional (res 1))
(setf *world* nil)
(defsphere 0 -300 -1200 200 .8)
(defsphere -80 -150 -1200 200 .7)
(defsphere 70 -100 -1200 200 .9)
(do ((x -2 (1+ x)))
((> x 2))
(do ((z 2 (1+ z)))
((> z 7))
(defsphere (* x 200) 300 (* z -400) 40 .75)))
(tracer (make-pathname :name "spheres.pgm") res))
Raw
spheres.pgm
P2 100 100 255
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
24
57
76
91
103
114
123
131
139
146
152
157
163
167
171
175
179
182
185
187
190
192
193
195
196
197
197
198
198
198
197
197
196
195
193
192
190
187
185
182
179
175
171
167
163
157
152
146
139
131
123
114
103
91
76
57
24
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
33
62
80
94
106
116
126
134
141
148
154
159
164
169
173
177
181
184
187
189
191
193
195
196
197
198
199
199
200
199
199
198
197
196
195
193
191
189
187
184
181
177
173
169
164
159
154
148
141
134
126
116
106
94
80
62
33
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
39
65
83
96
108
118
127
135
143
149
155
161
166
170
175
178
182
185
188
190
193
195
196
198
199
200
200
201
201
201
200
200
199
198
196
195
193
190
188
185
182
178
175
170
166
161
155
149
143
135
127
118
108
96
83
65
39
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
44
68
85
98
110
120
129
137
144
151
157
162
167
172
176
180
183
186
189
192
194
196
197
199
200
201
201
202
202
202
201
201
200
199
197
196
194
192
189
186
183
180
176
172
167
162
157
151
144
137
129
120
110
98
85
68
44
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
47
70
86
100
111
121
130
138
145
152
158
163
168
173
177
181
184
187
190
192
195
197
198
200
201
202
202
203
203
203
202
202
201
200
198
197
195
192
190
187
184
181
177
173
168
163
158
152
145
138
130
121
111
100
86
70
47
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
19
40
52
62
69
112
122
131
139
146
152
158
164
169
173
177
181
185
188
191
193
195
197
199
200
201
202
203
203
203
203
203
202
201
200
199
197
195
193
191
188
185
181
177
173
169
164
158
152
146
139
131
122
112
101
87
71
48
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
27
45
57
66
74
80
86
91
95
139
146
153
159
164
169
174
178
182
185
188
191
193
196
198
199
201
202
203
203
204
204
204
203
203
202
201
199
198
196
193
191
188
185
182
178
174
169
164
159
153
146
139
131
122
112
101
88
71
49
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
30
47
59
69
77
84
89
94
99
103
106
109
153
159
164
169
174
178
182
185
188
191
194
196
198
199
201
202
203
203
204
204
204
203
203
202
201
199
198
196
194
191
188
185
182
178
174
169
164
159
153
146
139
131
122
113
101
88
71
49
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
31
49
61
71
79
86
92
97
102
106
110
113
116
119
121
122
169
174
178
182
185
188
191
194
196
198
199
201
202
203
203
204
204
204
203
203
202
201
199
198
196
194
191
188
185
182
178
174
169
164
159
153
146
139
131
122
112
101
87
71
48
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
29
48
61
72
80
88
94
100
105
109
113
116
119
122
125
127
128
130
131
177
181
185
188
191
193
195
197
199
200
202
202
203
203
204
203
203
202
202
200
199
197
195
193
191
188
185
181
177
173
169
164
158
152
146
138
130
121
111
100
86
69
46
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
24
47
61
72
81
88
95
101
106
111
115
119
122
125
128
130
132
134
135
136
137
137
184
187
190
193
195
197
198
200
201
202
203
203
203
203
203
202
201
200
198
197
195
193
190
187
184
181
177
172
168
163
157
151
145
137
129
120
110
98
84
67
42
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
14
43
59
70
80
88
95
102
107
112
117
121
124
127
130
133
135
137
138
140
141
142
142
142
142
189
192
194
196
198
199
200
201
202
202
202
202
202
201
200
199
198
196
194
192
189
186
183
180
176
171
167
162
156
150
143
136
128
119
108
96
82
64
37
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
37
55
68
78
87
95
101
107
113
117
122
126
129
132
135
137
140
141
143
144
145
146
146
147
147
146
146
193
195
196
198
199
200
201
201
201
201
201
200
199
198
196
195
193
191
188
185
182
178
174
170
165
160
155
148
142
134
126
117
106
94
79
60
30
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
28
50
65
76
85
93
101
107
113
118
122
126
130
134
137
139
142
144
145
147
148
149
150
150
151
151
150
150
149
148
195
197
198
199
199
200
200
200
199
199
198
197
195
193
191
189
187
184
180
177
173
169
164
159
153
147
140
116
109
102
94
84
73
58
35
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
43
60
72
83
91
99
106
112
117
122
127
131
134
138
141
143
145
147
149
151
152
153
154
154
154
154
154
154
153
152
151
149
196
197
198
198
198
198
198
197
196
195
193
192
190
187
185
182
179
175
171
167
162
143
139
136
131
127
121
115
107
99
89
77
62
41
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
32
53
67
79
88
97
104
110
116
122
126
131
135
138
141
144
147
149
151
153
154
155
156
157
158
158
158
157
157
156
155
154
152
151
195
196
196
196
196
196
195
194
193
192
190
188
185
183
180
176
173
158
156
154
151
148
145
141
136
131
125
119
111
102
92
80
65
43
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5
44
61
74
84
93
101
108
115
120
125
130
134
138
142
145
147
150
152
154
156
157
158
159
160
161
161
161
161
160
159
158
157
156
154
152
150
194
194
194
194
193
192
191
189
188
186
183
180
168
168
167
165
164
162
159
157
153
149
145
140
135
129
122
114
104
94
81
65
43
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
29
52
67
79
89
98
105
112
118
124
129
133
137
141
145
148
150
153
155
157
159
160
161
162
163
163
164
164
163
163
162
161
160
159
157
155
153
150
147
192
191
191
190
188
187
185
174
175
175
175
175
174
172
171
169
167
164
161
157
153
148
143
137
131
123
115
105
94
81
64
39
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
40
59
73
84
94
102
109
116
122
127
132
136
140
144
147
150
153
156
158
160
161
163
164
165
165
166
166
166
166
165
165
164
163
161
159
158
155
153
150
147
143
188
187
177
178
180
181
181
181
181
181
180
179
177
175
173
171
167
164
160
156
151
145
139
132
124
115
105
93
79
61
31
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
19
48
65
78
88
97
105
112
119
125
130
135
139
143
147
150
153
156
158
160
162
164
165
166
167
168
168
168
168
168
168
167
166
165
164
162
160
158
155
153
149
146
179
181
183
184
186
187
187
187
187
187
186
185
183
181
179
177
174
170
166
162
157
152
146
140
132
124
115
104
91
76
55
14
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
31
54
69
81
92
100
108
115
121
127
132
137
141
145
149
152
155
158
160
162
164
166
167
168
169
170
170
170
170
170
170
169
168
167
166
164
162
160
158
155
152
148
184
186
188
190
191
192
192
193
192
192
191
190
189
187
185
182
179
176
172
168
164
158
153
146
139
132
123
113
101
87
70
46
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
39
59
73
85
95
103
111
118
124
129
134
139
143
147
151
154
157
160
162
164
166
167
169
170
171
172
172
172
172
172
172
171
170
169
167
166
164
162
159
157
154
150
189
191
193
195
196
197
197
197
197
197
196
195
194
192
190
187
184
181
178
174
169
164
159
153
146
138
130
121
110
97
82
63
31
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
44
63
76
88
97
106
113
120
126
131
136
141
145
149
152
156
159
161
164
166
167
169
170
172
172
173
174
174
174
174
173
172
172
170
169
167
166
164
161
158
156
191
194
196
198
199
200
201
202
202
202
201
201
200
198
196
194
192
189
186
183
179
174
169
164
158
152
144
136
127
117
106
92
75
51
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
18
49
66
79
90
99
107
115
121
127
133
138
142
147
150
154
157
160
163
165
167
169
170
172
173
174
174
175
175
175
175
174
174
173
172
170
169
167
165
163
160
157
196
198
200
202
203
205
205
206
206
206
205
205
204
202
201
199
196
193
190
187
183
179
174
169
163
157
150
142
133
124
113
100
85
65
34
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
26
52
68
81
92
101
109
116
123
129
134
139
144
148
152
155
158
161
164
166
168
170
172
173
174
175
176
176
176
176
176
176
175
174
173
172
170
168
166
164
161
158
200
202
204
206
207
208
209
209
210
210
209
208
207
206
204
202
200
197
194
191
187
183
178
173
168
161
155
147
139
130
119
107
93
75
51
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
30
54
70
83
93
102
110
117
124
130
135
140
145
149
153
156
159
162
165
167
169
171
172
174
175
176
176
177
177
177
177
176
176
175
174
172
171
169
167
165
162
200
203
205
207
209
211
212
212
213
213
213
212
212
211
209
208
206
203
201
198
195
191
187
182
177
172
166
159
152
144
135
124
113
100
83
62
26
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
33
56
72
84
94
103
111
118
125
131
136
141
145
150
153
157
160
163
165
168
170
171
173
174
176
176
177
178
178
178
178
177
176
176
175
173
172
170
168
165
163
204
206
209
211
212
214
215
215
216
216
216
215
215
214
212
211
209
207
204
201
198
194
190
186
181
175
169
163
156
148
139
129
118
105
90
71
43
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
35
57
72
85
95
104
112
119
125
131
137
141
146
150
154
157
160
163
166
168
170
172
174
175
176
177
178
178
178
178
178
178
177
176
175
174
172
170
168
166
203
206
209
211
213
215
216
217
218
219
219
219
218
217
216
215
214
212
209
207
204
201
197
193
189
184
178
173
166
159
152
143
133
123
110
96
78
54
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
35
57
73
85
95
104
112
119
126
131
137
142
146
150
154
157
161
163
166
168
170
172
174
175
176
177
178
178
178
178
178
178
177
176
175
174
172
171
168
166
206
209
212
214
216
217
219
220
220
221
221
221
221
220
219
218
216
214
212
209
206
203
200
196
191
186
181
176
169
162
155
146
137
127
115
101
84
62
24
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
34
57
72
85
95
104
112
119
125
131
137
142
146
150
154
157
161
163
166
168
170
172
174
175
176
177
178
178
178
178
178
178
177
176
175
174
172
171
168
166
208
211
214
216
218
219
221
222
223
223
223
223
223
222
221
220
218
216
214
211
209
205
202
198
194
189
184
178
172
165
158
149
140
130
118
105
89
69
38
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
33
56
72
84
94
103
111
119
125
131
136
141
146
150
154
157
160
163
166
168
170
172
174
175
176
177
178
178
178
178
178
178
177
176
175
174
172
170
168
207
210
213
216
218
220
221
223
224
224
225
225
225
224
224
223
221
220
218
216
213
210
207
204
200
196
191
186
180
174
167
160
152
143
133
121
108
93
74
46
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
30
54
70
83
93
103
111
118
124
130
136
141
145
149
153
157
160
163
165
168
170
171
173
174
176
176
177
178
178
178
178
177
177
176
175
173
172
170
168
208
212
215
217
219
221
223
224
225
226
226
226
226
226
225
224
223
221
219
217
215
212
209
205
201
197
193
187
182
176
169
162
154
145
135
124
111
96
78
52
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
25
52
68
81
92
101
109
117
123
129
135
140
144
149
152
156
159
162
165
167
169
171
172
174
175
176
176
177
177
177
177
177
176
175
174
173
171
169
167
210
213
216
218
221
222
224
225
226
227
227
228
227
227
226
225
224
222
221
218
216
213
210
207
203
198
194
189
183
177
171
163
155
147
137
126
113
99
81
56
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
17
49
66
79
90
100
108
115
122
128
134
139
143
147
151
155
158
161
164
166
168
170
172
173
174
175
176
176
176
176
176
176
175
174
173
172
170
168
166
211
214
217
219
221
223
225
226
227
228
228
228
228
228
227
226
225
223
222
219
217
214
211
207
204
199
195
190
184
178
172
164
157
148
138
127
115
100
83
59
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
44
63
77
88
98
106
114
120
127
132
137
142
146
150
154
157
160
162
165
167
169
170
172
173
174
175
175
175
175
175
175
174
173
172
171
169
167
208
211
215
217
220
222
224
226
227
228
229
229
229
229
229
228
227
226
224
222
220
218
215
212
208
204
200
195
190
185
179
172
165
157
149
139
128
116
102
84
61
17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
38
59
74
85
95
104
112
118
125
130
136
140
145
148
152
155
158
161
163
165
167
169
170
172
172
173
174
174
174
174
173
173
172
171
169
168
166
208
212
215
218
220
222
224
226
227
228
229
229
229
229
229
228
227
226
224
222
220
218
215
212
208
205
200
196
191
185
179
173
166
158
149
139
129
116
102
85
62
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
30
54
70
82
92
101
109
116
122
128
133
138
143
147
150
154
157
159
162
164
166
167
169
170
171
172
172
172
172
172
172
171
170
169
168
166
164
208
212
215
218
220
222
224
226
227
228
229
229
229
229
229
228
227
226
224
223
220
218
215
212
209
205
200
196
191
185
179
173
166
158
149
139
129
116
102
85
62
19
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
17
48
65
78
89
98
106
113
120
126
131
136
140
144
148
152
155
157
160
162
164
166
167
168
169
170
170
171
171
170
170
169
168
167
166
164
204
208
212
215
218
220
222
224
226
227
228
229
229
229
229
229
228
227
226
224
222
220
218
215
212
208
204
200
196
191
185
179
172
165
157
149
139
128
116
101
84
61
15
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
40
59
73
85
94
103
110
117
123
128
133
138
142
146
149
152
155
158
160
162
163
165
166
167
168
168
168
169
168
168
167
166
165
164
162
204
207
211
214
217
220
222
224
225
227
227
228
229
229
229
228
227
226
225
224
222
220
217
214
211
208
204
200
195
190
184
178
172
164
156
148
138
127
115
100
82
58
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
28
52
68
80
90
99
107
114
120
125
130
135
139
143
147
150
153
155
157
159
161
162
164
165
165
166
166
166
166
166
165
164
163
161
160
203
207
210
213
216
219
221
223
224
226
227
227
228
228
228
227
227
226
224
223
221
219
216
213
210
207
203
199
194
189
183
177
171
163
155
146
137
126
113
98
80
55
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
44
61
75
85
95
103
110
116
122
127
132
136
140
144
147
150
152
155
157
158
160
161
162
163
163
164
164
163
163
162
161
160
159
197
201
205
209
212
215
218
220
222
223
225
226
226
227
227
227
226
226
225
223
222
220
218
215
212
209
206
202
197
193
188
182
176
169
162
154
145
135
124
111
95
77
50
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
31
53
68
80
90
98
105
112
118
123
128
133
137
140
144
147
149
152
154
155
157
158
159
160
160
161
161
161
160
159
158
157
156
196
200
204
208
211
214
216
218
220
222
223
224
225
225
226
225
225
224
223
222
220
218
216
214
211
208
204
200
196
191
186
180
174
167
160
152
143
132
121
108
92
72
43
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
43
60
73
84
93
101
107
114
119
124
129
133
137
140
143
146
148
150
152
154
155
156
157
157
158
158
157
157
156
155
154
152
194
198
202
206
209
212
214
217
219
220
222
223
223
224
224
224
223
223
222
220
219
217
214
212
209
206
202
198
194
189
184
178
172
165
157
149
140
130
118
104
88
67
34
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
27
50
65
77
87
95
102
109
115
120
125
129
133
136
139
142
144
147
148
150
151
152
153
154
154
154
154
153
153
152
150
186
191
196
200
204
207
210
212
215
217
218
220
221
221
222
222
222
221
221
220
218
217
215
212
210
207
204
200
196
192
187
181
176
169
162
155
146
137
126
114
100
83
60
16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
37
56
69
80
89
97
103
109
115
120
124
128
132
135
138
140
143
145
146
147
149
149
150
150
150
150
150
149
148
146
184
189
193
197
201
204
207
210
212
214
216
217
218
219
220
220
219
219
218
217
216
214
212
210
207
205
201
198
193
189
184
179
173
166
159
151
143
133
122
110
95
76
51
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13
43
60
72
81
90
97
104
109
115
119
123
127
130
133
136
138
140
142
143
144
145
146
146
146
146
145
145
143
142
181
186
190
194
198
202
205
207
210
212
213
215
216
216
217
217
217
216
216
215
213
212
210
207
205
202
198
195
191
186
181
176
169
163
156
148
139
129
117
104
89
69
39
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
24
47
62
73
82
90
97
103
109
114
118
122
125
128
131
133
135
137
139
140
141
141
141
141
141
141
140
139
171
177
182
187
191
195
198
202
204
207
209
210
212
213
214
214
214
214
214
213
212
210
209
207
204
202
199
195
191
187
183
177
172
166
159
152
143
134
124
112
98
81
59
15
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
29
49
63
73
82
90
96
102
107
112
116
119
123
126
128
130
132
133
135
135
136
136
136
136
136
135
134
167
173
178
183
188
191
195
198
201
203
205
207
208
209
210
211
211
211
210
209
208
207
205
203
201
198
195
192
188
183
179
174
168
162
155
147
138
129
118
106
91
72
46
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
31
50
63
73
81
88
95
100
105
109
113
117
119
122
124
126
128
129
130
131
131
131
131
130
129
128
163
169
174
179
183
187
191
194
197
199
202
203
205
206
207
207
207
207
207
206
205
203
202
199
197
194
191
188
184
179
174
169
163
157
150
142
133
123
111
98
82
61
25
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
31
49
61
71
79
86
92
97
102
106
110
113
116
118
120
121
123
124
124
125
125
124
124
123
151
157
164
169
174
179
183
187
190
193
195
197
199
201
202
203
203
203
203
203
202
201
199
197
195
193
190
187
183
179
175
170
164
158
151
144
136
127
116
104
90
72
46
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
28
46
59
68
76
83
89
94
98
102
105
108
111
113
115
116
117
118
118
118
118
117
116
144
152
158
164
169
174
178
182
185
188
191
193
195
196
197
198
199
199
199
198
197
196
195
193
191
188
185
182
178
174
170
164
159
153
146
138
129
119
108
95
79
58
19
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
21
42
54
64
72
78
84
89
93
97
100
103
105
107
108
109
110
111
111
110
110
108
138
145
152
158
163
168
173
176
180
183
186
188
190
191
192
193
194
194
194
193
192
191
190
188
186
183
180
177
173
169
164
159
153
146
139
131
122
111
99
85
66
39
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
34
48
58
66
73
78
83
87
91
94
96
98
100
101
102
102
102
102
101
100
130
138
145
151
157
162
167
171
174
177
180
182
184
186
187
188
188
189
188
188
187
186
184
182
180
177
174
171
167
163
158
152
146
139
132
123
113
102
89
72
49
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
22
39
50
59
66
71
76
80
83
86
88
90
91
92
93
93
92
91
112
122
130
137
144
150
155
160
164
168
171
174
176
178
180
181
182
183
183
183
182
181
180
178
176
174
171
168
164
160
156
151
145
138
131
123
114
103
91
76
55
17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
25
39
49
56
62
67
71
74
76
78
80
81
81
81
81
80
101
112
121
129
136
142
148
153
157
161
164
167
170
172
173
175
176
176
176
176
176
175
173
172
170
167
164
161
157
153
148
143
137
130
122
114
104
92
77
59
29
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
19
34
43
49
55
59
62
64
66
67
68
68
67
66
89
101
111
119
127
133
139
145
149
153
157
160
162
165
166
168
169
169
169
169
169
168
166
165
163
160
157
153
150
145
140
134
128
120
112
103
91
78
60
33
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
19
30
37
42
45
48
49
50
50
49
48
73
87
98
108
116
124
130
135
140
145
148
152
154
157
158
160
161
161
162
162
161
160
159
157
155
152
149
145
141
136
131
124
117
110
100
89
76
60
34
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
11
16
19
19
16
18
52
70
84
95
104
112
119
125
130
135
139
142
145
148
150
151
152
153
153
153
152
151
150
148
146
143
139
136
131
126
120
113
106
97
86
73
57
30
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
46
65
79
90
99
107
113
119
124
129
132
135
138
140
142
143
144
144
144
143
142
140
138
136
133
129
125
120
114
108
100
92
81
68
51
21
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
36
57
72
83
92
100
106
112
117
121
124
127
129
131
132
133
133
133
132
131
129
127
125
121
117
113
107
101
94
85
74
61
42
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
16
46
62
74
83
91
97
103
107
111
114
117
119
120
121
121
121
120
119
117
115
112
108
104
98
92
85
76
65
50
27
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
26
48
61
71
79
86
91
96
100
102
105
106
107
107
107
106
105
103
100
97
92
87
81
73
63
51
32
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
21
42
55
64
71
77
81
85
87
89
90
91
91
90
88
85
82
78
72
66
57
45
28
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
26
41
50
57
61
65
68
69
70
69
68
66
62
58
51
43
30
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
15
26
32
35
36
35
33
28
18
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
83
125
119
50
0
0
0
0
0
0
0
0
0
41
117
125
85
0
0
0
0
0
0
0
0
0
0
105
127
105
0
0
0
0
0
0
0
0
0
0
85
125
117
41
0
0
0
0
0
0
0
0
0
50
119
125
83
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
61
149
176
171
133
0
0
0
0
0
0
0
0
0
131
171
176
150
61
0
0
0
0
0
0
0
0
104
162
177
162
104
0
0
0
0
0
0
0
0
61
150
176
171
131
0
0
0
0
0
0
0
0
0
133
171
176
149
61
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
96
166
190
185
150
22
0
0
0
0
0
0
0
15
150
185
190
166
93
0
0
0
0
0
0
0
0
127
177
19
177
127
0
0
0
0
0
0
0
0
93
166
190
185
150
15
0
0
0
0
0
0
0
22
150
185
190
166
96
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
28
119
141
134
93
151
176
171
131
0
0
0
0
0
0
0
99
136
140
114
176
149
59
0
0
0
0
0
0
0
0
68
127
142
127
68
0
0
0
0
0
0
0
0
59
149
176
114
140
136
99
0
0
0
0
0
0
0
131
171
176
151
93
134
141
119
28
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
114
162
179
173
143
59
126
118
41
0
0
0
0
0
0
76
148
175
178
158
102
83
0
0
0
0
0
0
0
0
0
129
168
179
168
129
0
0
0
0
0
0
0
0
0
83
102
158
178
175
148
76
0
0
0
0
0
0
41
118
126
59
143
173
179
162
114
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
133
176
191
185
157
87
0
0
0
0
0
0
0
0
0
102
163
187
190
171
121
0
0
0
0
0
0
0
0
0
42
145
181
191
181
145
42
0
0
0
0
0
0
0
0
0
121
171
190
187
163
102
0
0
0
0
0
0
0
0
0
87
157
185
191
176
133
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
78
85
54
0
122
167
182
176
146
63
0
0
0
0
0
0
0
0
73
85
61
179
181
161
106
0
0
0
0
0
0
0
0
0
0
134
68
86
68
134
0
0
0
0
0
0
0
0
0
0
106
161
181
179
61
85
73
0
0
0
0
0
0
0
0
63
146
176
182
167
122
0
54
85
78
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
57
122
146
149
134
90
67
131
150
142
101
0
0
0
0
0
0
0
19
115
143
150
137
98
148
122
18
0
0
0
0
0
0
0
0
0
0
107
140
150
140
107
0
0
0
0
0
0
0
0
0
0
18
122
148
98
137
150
143
115
19
0
0
0
0
0
0
0
101
142
150
131
67
90
134
149
146
122
57
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
115
157
176
179
165
132
47
0
63
39
0
0
0
0
0
0
0
0
101
152
174
179
169
139
67
0
0
0
0
0
0
0
0
0
0
0
85
145
171
179
171
145
85
0
0
0
0
0
0
0
0
0
0
0
67
139
169
179
174
152
101
0
0
0
0
0
0
0
0
39
63
0
47
132
165
179
176
157
115
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
32
133
171
188
190
177
146
77
0
0
0
0
0
0
0
0
0
0
0
121
165
186
190
180
153
93
0
0
0
0
0
0
0
0
0
0
0
107
159
183
191
183
159
107
0
0
0
0
0
0
0
0
0
0
0
93
153
180
190
186
165
121
0
0
0
0
0
0
0
0
0
0
0
77
146
177
190
188
171
133
32
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
18
130
168
185
186
173
141
66
0
0
0
0
0
0
0
0
0
0
0
117
162
183
187
177
148
85
0
0
0
0
0
0
0
0
0
0
0
101
155
180
187
180
155
101
0
0
0
0
0
0
0
0
0
0
0
85
148
177
187
183
162
117
0
0
0
0
0
0
0
0
0
0
0
66
141
173
186
185
168
130
18
0
0
0
0
0
0
0
0
0
0
0
0
0
0
41
49
0
0
0
0
103
147
166
167
152
114
0
0
0
0
0
0
0
0
0
0
35
50
8
140
164
168
157
123
19
0
0
0
0
0
0
0
0
0
0
0
61
132
26
50
26
132
61
0
0
0
0
0
0
0
0
0
0
0
19
123
157
168
164
140
8
50
35
0
0
0
0
0
0
0
0
0
0
114
152
167
166
147
103
0
0
0
0
49
41
0
0
0
0
0
0
0
63
107
125
128
115
82
0
0
0
100
125
126
105
24
0
0
0
0
0
0
0
0
42
101
123
128
118
88
122
128
111
55
0
0
0
0
0
0
0
0
0
0
0
0
0
95
121
128
121
95
0
0
0
0
0
0
0
0
0
0
0
0
0
55
111
128
122
88
118
128
123
101
42
0
0
0
0
0
0
0
0
24
105
126
125
100
0
0
0
82
115
128
125
107
63
0
0
0
0
59
120
148
161
163
153
129
81
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
110
144
160
163
155
134
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
100
139
158
164
158
139
100
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
134
155
163
160
144
110
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
81
129
153
163
161
148
120
59
0
0
0
103
146
170
181
182
173
152
113
0
0
0
0
0
0
0
0
0
0
0
0
0
0
84
138
166
179
182
175
156
121
30
0
0
0
0
0
0
0
0
0
0
0
0
0
61
129
161
178
183
178
161
129
61
0
0
0
0
0
0
0
0
0
0
0
0
0
30
121
156
175
182
179
166
138
84
0
0
0
0
0
0
0
0
0
0
0
0
0
0
113
152
173
182
181
170
146
103
0
0
0
119
157
179
189
190
181
161
124
37
0
0
0
0
0
0
0
0
0
0
0
0
0
101
149
175
188
191
183
165
132
61
0
0
0
0
0
0
0
0
0
0
0
0
0
82
140
170
186
191
186
170
140
82
0
0
0
0
0
0
0
0
0
0
0
0
0
61
132
165
183
191
188
175
149
101
0
0
0
0
0
0
0
0
0
0
0
0
0
37
124
161
181
190
189
179
157
119
0
0
0
118
157
178
188
188
179
158
120
15
0
0
0
0
0
0
0
0
0
0
0
0
0
100
148
173
186
189
182
163
129
54
0
0
0
0
0
0
0
0
0
0
0
0
0
79
138
168
184
189
184
168
138
79
0
0
0
0
0
0
0
0
0
0
0
0
0
54
129
163
182
189
186
173
148
100
0
0
0
0
0
0
0
0
0
0
0
0
0
15
120
158
179
188
188
178
157
118
0
0
0
101
144
166
177
176
166
143
99
0
0
0
0
0
0
0
0
0
0
0
0
0
0
78
134
161
175
177
169
149
110
0
0
0
0
0
0
0
0
0
0
0
0
0
0
45
122
156
172
178
172
156
122
45
0
0
0
0
0
0
0
0
0
0
0
0
0
0
110
149
169
177
175
161
134
78
0
0
0
0
0
0
0
0
0
0
0
0
0
0
99
143
166
176
177
166
144
101
0
0
0
55
115
142
153
153
140
111
39
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
102
136
151
154
144
120
65
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
85
128
148
154
148
128
85
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
65
120
144
154
151
136
102
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
39
111
140
153
153
142
115
55
0
0
0
0
49
95
110
109
90
26
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
85
108
111
97
54
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
72
103
112
103
72
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
54
97
111
108
85
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
26
90
109
110
95
49
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
62
92
104
104
94
67
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
30
81
100
105
100
81
30
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
67
94
104
104
92
62
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
82
116
134
142
142
135
117
85
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
50
102
127
139
143
139
127
102
50
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
85
117
135
142
142
134
116
82
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
74
119
144
159
166
166
159
145
119
73
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
99
133
153
163
167
163
153
133
99
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
73
119
145
159
166
166
159
144
119
74
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
104
140
162
175
181
180
174
161
138
101
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
69
122
151
168
178
181
178
168
151
122
69
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
101
138
161
174
180
181
175
162
140
104
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
58
119
151
171
183
189
188
182
169
148
114
41
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
88
134
160
177
186
189
186
177
160
134
88
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
41
114
148
169
182
188
189
183
171
151
119
58
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
67
123
154
174
185
191
190
184
171
150
116
47
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
93
137
163
179
188
191
188
179
163
137
93
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
47
116
150
171
184
190
191
185
174
154
123
67
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
59
119
150
170
182
187
186
180
166
144
109
22
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
85
132
159
175
185
188
185
175
159
132
85
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
22
109
144
166
180
186
187
182
170
150
119
59
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
22
105
139
160
172
178
177
170
155
131
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
62
118
147
165
175
178
175
165
147
118
62
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
131
155
170
177
178
172
160
139
105
22
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
76
118
142
155
161
160
152
135
106
46
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
91
127
147
158
161
158
147
127
91
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
46
106
135
152
160
161
155
142
118
76
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
81
112
129
135
133
123
102
58
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
25
91
118
131
135
131
118
91
25
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
58
102
123
133
135
129
112
81
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
55
83
92
89
73
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
64
86
93
86
64
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
20
73
89
92
83
55
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment