-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathquicksort.js
262 lines (252 loc) · 24.9 KB
/
quicksort.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
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
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
'use strict';
/**
* author: Mirco Palese
* date: 3/02/2024
*
* Here we will move on to an intermediate sorting algorithm: quick sort.
* Quick sort is an efficient, recursive divide-and-conquer approach to sorting an array.
* In this method, a pivot value is chosen in the original array. The array is then partitioned
* into two subarrays of values less than and greater than the pivot value. We then combine
* the result of recursively calling the quick sort algorithm on both sub-arrays.
* This continues until the base case of an empty or single-item array is
* reached, which we return. The unwinding of the recursive calls return us the sorted array.
*/
const asyncQuickSort = async function (arr) {
if (arr.length <= 1) return arr;
const pivot = Math.round(arr.length / 2);
const less = [];
const greater = [];
const equal = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < arr[pivot]) less.push(arr[i]);
else if (arr[i] > arr[pivot]) greater.push(arr[i]);
else equal.push(arr[i]);
}
const promisesRes = [quickSort(less), quickSort(greater)];
let res = await Promise.all(promisesRes);
res = [res[0].flat(Infinity), ...equal, res[1].flat(Infinity)];
return res.flat(Infinity);
};
const quickSort = function (arr) {
if (arr.length <= 1) return arr;
const pivot = Math.round(arr.length / 2);
const less = [];
const greater = [];
const equal = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < arr[pivot]) less.push(arr[i]);
else if (arr[i] > arr[pivot]) greater.push(arr[i]);
else equal.push(arr[i]);
}
return [...quickSort(less), ...equal, ...quickSort(greater)];
};
(async () => {
console.time('timer0');
// let res = await asyncQuickSort([
// 1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92, 543, 54, 354, 35, 43, 653, 4532, 532, 6, 54, 6,
// 7, 78, 8, 4, 3, 4, 6, 764, 2, 3, 7, 786, 4, 345, 6, 54, 3, 43, 24, 5, 6, 5456, 7, 967, 5, 54, 34542, 6, 7, 4, 7,
// 756, 54, 5, 6, 4, 65, 46, 3, 2534, 63, 6, 45, 7, 54, 63, 456, 4, 756, 87, 89, 76, 54, 3, 2, 45, 6, 8, 99, 432, 432,
// 43, 2, 4, 5, 6, 7, 8, 9, 3, 4, 5, 56, 6, 6, 3, 45, 45, 23, 5, 43643, 654, 2, 45, 5, 4, 567, 3, 29, 546, 673, 6, 67,
// 5, 54, 65, 3, 6, 543, 63, 46, 34,
// ]);
// console.timeEnd('timer0');
console.time('timer1');
let res = quickSort([
416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254,
778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209,
17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134,
934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436,
839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611,
742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482,
992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399,
755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610,
924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480,
176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773,
890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442,
912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388,
453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694,
62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787,
573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413,
193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454,
839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259,
564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409,
384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982,
493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159,
300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535,
767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606,
254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750,
209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46,
134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174,
436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313,
611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166,
482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47,
399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469,
610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830,
480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180,
773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656,
442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215,
388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498,
694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643,
787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24,
413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681,
454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782,
259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22,
409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184,
982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251,
159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429,
535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537,
606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320,
750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996,
46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214,
174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789,
313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118,
166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481,
292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437,
958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937,
681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259,
199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381,
442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789,
119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633,
938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692,
990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705,
432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215,
681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416,
782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778,
582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17,
936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934,
448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839,
17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742,
537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992,
320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755,
996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924,
214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176,
789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890,
118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912,
481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453,
437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62,
937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573,
259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193,
381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839,
789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564,
633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384,
692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493,
705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300,
215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767,
416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254,
778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209,
17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134,
934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436,
839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611,
742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482,
992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399,
755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610,
924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480,
176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773,
890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442,
912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388,
453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694,
62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787,
573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413,
193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454,
839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259,
564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409,
384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982,
493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159,
300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535,
767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606,
254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750,
209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46,
134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174,
436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313,
611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166,
482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47,
399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469,
610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830,
480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180,
773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656,
442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215,
388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498,
694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643,
787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24,
413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681,
454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782,
259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22,
409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184,
982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251,
159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429,
535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537,
606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320,
750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996,
46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214,
174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789,
313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118,
166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481,
292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437,
958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937,
681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259,
199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381,
442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789,
119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633,
938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692,
990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705,
432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215,
681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416,
782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778,
582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17,
936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934,
448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839,
17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742,
537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992,
320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755,
996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924,
214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176,
789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890,
118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912,
481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453,
437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62,
937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573,
259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193,
381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839,
789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564,
633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384,
692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493,
705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300,
215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767,
416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254,
778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209,
17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134,
934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436,
839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611,
742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482,
992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399,
755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610,
924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480,
176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773,
890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442,
912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388,
453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694,
62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787,
573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413,
193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454,
839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259,
564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409,
384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982,
493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159,
300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535,
767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313, 611, 742, 537, 606,
254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166, 482, 992, 320, 750,
209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47, 399, 755, 996, 46,
134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469, 610, 924, 214, 174,
436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830, 480, 176, 789, 313,
611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180, 773, 890, 118, 166,
482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656, 442, 912, 481, 292, 47,
399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215, 388, 453, 437, 958, 469,
610, 924, 214, 174, 436, 839, 17, 429, 535, 767, 416, 782, 259, 564, 633, 938, 798, 498, 694, 62, 937, 681, 28, 830,
480, 176, 789, 313, 611, 742, 537, 606, 254, 778, 582, 22, 409, 384, 692, 990, 4, 643, 787, 573, 259, 199, 151, 180,
773, 890, 118, 166, 482, 992, 320, 750, 209, 17, 936, 184, 982, 493, 705, 432, 24, 413, 193, 381, 442, 103, 656,
442, 912, 481, 292, 47, 399, 755, 996, 46, 134, 934, 448, 251, 159, 300, 215, 681, 454, 839, 789, 119, 922, 215,
388, 453, 437, 958, 469, 610, 924, 214, 174, 436, 839, 17, 429, 535, 767,
]);
console.log(res);
console.timeEnd('timer1');
})();