-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbubblesort.cpp
63 lines (47 loc) · 74.1 KB
/
bubblesort.cpp
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
#include<iostream>
#include<conio.h>
#include<ctime>
using namespace std;
int bubblesort(int arr[],int size);
int main()
{
int n = 20000;
int a[n] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,3,4,4,5,11,11,12,12,14,16,17,17,20,21,23,30,30,31,37,39,41,41,42,43,44,44,45,47,47,48,48,50,50,52,53,55,58,59,62,63,63,69,69,70,73,79,80,81,82,82,85,94,99,101,105,108,109,109,112,112,113,114,114,115,116,118,118,120,122,125,135,137,140,143,143,147,148,150,152,154,157,160,161,165,166,167,170,171,183,184,188,193,199,199,200,202,203,206,214,219,228,231,231,233,234,236,236,238,240,242,244,249,250,250,252,253,254,259,260,263,264,264,266,270,270,272,272,275,275,275,277,280,281,283,283,286,286,286,286,287,287,288,289,292,295,298,300,300,303,303,305,314,316,320,324,324,326,327,327,331,333,333,333,335,337,338,340,345,347,347,348,350,351,352,353,354,356,357,358,361,362,363,364,366,368,375,375,376,377,377,377,382,383,384,385,385,387,388,392,395,396,398,400,401,401,402,404,404,404,406,407,408,412,412,413,417,426,426,427,428,430,430,431,431,434,435,439,441,442,444,451,454,456,457,459,462,463,463,464,470,471,471,474,474,474,475,476,476,485,486,487,493,493,496,497,498,501,503,509,514,514,515,517,519,521,529,529,529,530,533,539,539,542,554,555,555,559,560,564,568,568,570,570,573,575,576,576,577,580,582,588,589,594,595,600,603,608,613,615,615,617,619,620,622,624,625,628,628,629,632,634,635,635,638,639,640,643,643,650,650,650,652,656,665,670,673,673,673,677,678,680,688,689,691,693,695,697,698,699,699,702,705,707,710,712,712,713,714,716,716,717,718,718,718,720,723,723,723,724,727,727,734,747,747,748,751,752,752,754,754,757,758,759,760,762,762,764,768,770,771,773,776,777,780,782,783,784,784,786,787,790,793,802,803,803,807,815,816,816,819,821,830,831,837,839,842,842,843,846,851,852,856,857,858,858,858,862,863,871,876,878,879,880,880,882,882,886,888,892,893,893,894,895,900,901,901,904,905,905,906,916,916,917,918,921,932,937,938,939,940,942,943,944,945,947,948,948,952,953,955,957,961,962,965,969,971,971,973,974,974,977,978,983,984,986,988,992,993,994,996,998,998,1001,1001,1002,1002,1002,1004,1005,1006,1011,1013,1014,1017,1018,1018,1018,1024,1024,1025,1025,1027,1027,1029,1034,1036,1037,1039,1043,1045,1045,1047,1047,1049,1050,1052,1056,1059,1061,1063,1064,1064,1066,1068,1068,1068,1072,1075,1076,1076,1081,1086,1101,1108,1110,1111,1111,1112,1116,1121,1121,1127,1129,1129,1134,1136,1139,1139,1140,1140,1141,1142,1143,1148,1149,1150,1152,1153,1160,1161,1162,1162,1164,1170,1172,1173,1173,1173,1177,1177,1177,1178,1180,1180,1182,1182,1185,1189,1192,1192,1196,1196,1198,1200,1202,1203,1203,1204,1204,1210,1213,1216,1217,1219,1219,1222,1233,1233,1234,1235,1235,1236,1236,1241,1243,1244,1251,1253,1258,1260,1263,1263,1265,1267,1269,1274,1283,1286,1286,1287,1287,1289,1292,1292,1297,1302,1302,1303,1303,1303,1308,1312,1316,1316,1317,1320,1321,1321,1324,1325,1325,1328,1329,1331,1332,1332,1332,1337,1338,1338,1339,1343,1343,1345,1346,1348,1351,1352,1352,1353,1353,1356,1356,1361,1367,1368,1368,1371,1372,1372,1372,1373,1375,1375,1375,1375,1378,1379,1379,1381,1383,1385,1385,1385,1386,1386,1388,1392,1392,1394,1395,1397,1398,1398,1398,1400,1404,1407,1408,1408,1409,1410,1413,1413,1414,1415,1416,1422,1423,1425,1425,1427,1429,1430,1430,1430,1432,1433,1433,1433,1434,1435,1439,1448,1448,1449,1458,1459,1461,1464,1466,1475,1476,1476,1476,1478,1479,1480,1482,1482,1482,1483,1484,1486,1488,1488,1489,1489,1491,1495,1501,1501,1502,1502,1503,1504,1505,1507,1508,1510,1513,1517,1521,1521,1523,1524,1526,1526,1531,1532,1536,1539,1541,1543,1544,1545,1551,1552,1555,1557,1559,1561,1564,1567,1570,1576,1577,1578,1578,1583,1584,1584,1586,1588,1588,1589,1591,1593,1596,1601,1602,1603,1606,1607,1608,1610,1611,1613,1616,1617,1617,1621,1622,1623,1624,1626,1626,1628,1630,1630,1631,1631,1633,1633,1638,1640,1642,1644,1645,1650,1650,1653,1653,1656,1656,1660,1661,1663,1667,1668,1670,1673,1677,1681,1683,1683,1685,1687,1687,1688,1688,1690,1694,1699,1700,1703,1703,1704,1705,1706,1708,1709,1710,1714,1723,1726,1728,1729,1729,1729,1730,1731,1731,1735,1737,1737,1738,1739,1741,1743,1746,1748,1755,1755,1755,1756,1756,1757,1761,1763,1763,1763,1764,1764,1765,1766,1770,1771,1771,1773,1773,1777,1778,1778,1778,1780,1781,1781,1784,1784,1785,1792,1793,1793,1795,1797,1799,1800,1802,1803,1805,1806,1811,1812,1812,1812,1813,1815,1818,1820,1820,1820,1824,1825,1827,1833,1834,1835,1837,1841,1841,1843,1843,1844,1845,1846,1847,1849,1850,1851,1853,1853,1858,1862,1863,1864,1864,1868,1869,1870,1870,1873,1874,1874,1875,1875,1876,1877,1880,1893,1893,1898,1900,1900,1901,1902,1903,1905,1909,1913,1914,1918,1921,1926,1934,1934,1936,1937,1945,1947,1947,1952,1959,1959,1961,1962,1964,1965,1971,1972,1972,1974,1976,1981,1982,1985,1988,1989,1990,1991,1993,1996,2000,2002,2002,2005,2005,2007,2009,2012,2015,2015,2016,2017,2019,2022,2024,2026,2030,2031,2033,2034,2035,2035,2035,2036,2041,2041,2043,2044,2044,2046,2046,2054,2059,2063,2063,2064,2068,2071,2071,2071,2071,2073,2074,2082,2085,2086,2087,2087,2089,2093,2093,2095,2096,2098,2100,2102,2105,2113,2114,2115,2116,2118,2118,2124,2132,2133,2133,2138,2139,2139,2140,2141,2146,2148,2148,2149,2152,2154,2156,2158,2160,2163,2164,2164,2164,2164,2165,2165,2166,2168,2171,2171,2175,2175,2182,2183,2184,2184,2184,2187,2188,2189,2196,2197,2197,2197,2201,2207,2208,2209,2213,2215,2217,2219,2220,2221,2223,2226,2227,2229,2231,2231,2232,2234,2239,2242,2243,2247,2250,2260,2262,2263,2263,2265,2265,2269,2275,2277,2279,2280,2281,2281,2285,2286,2287,2288,2288,2295,2296,2296,2298,2299,2303,2304,2305,2306,2306,2309,2311,2316,2318,2320,2321,2322,2322,2323,2324,2325,2327,2328,2328,2331,2332,2334,2334,2336,2337,2339,2342,2355,2356,2359,2360,2360,2363,2364,2367,2369,2369,2370,2373,2373,2374,2375,2376,2377,2378,2380,2380,2381,2382,2383,2384,2388,2388,2389,2390,2393,2393,2395,2397,2399,2399,2399,2403,2407,2411,2411,2417,2419,2419,2420,2422,2425,2426,2426,2428,2429,2430,2430,2432,2433,2437,2437,2440,2444,2446,2448,2458,2463,2464,2465,2466,2469,2470,2471,2473,2477,2478,2479,2481,2482,2486,2486,2488,2491,2496,2499,2499,2501,2502,2504,2504,2509,2509,2511,2511,2517,2517,2517,2520,2523,2524,2527,2527,2533,2533,2536,2537,2540,2541,2542,2547,2549,2551,2556,2567,2567,2567,2570,2580,2581,2587,2587,2588,2589,2593,2593,2594,2594,2596,2598,2605,2606,2608,2608,2610,2610,2612,2620,2622,2623,2624,2627,2628,2634,2634,2637,2638,2638,2639,2641,2642,2646,2646,2646,2647,2648,2650,2652,2656,2657,2657,2658,2660,2662,2663,2669,2670,2671,2672,2673,2674,2675,2676,2677,2682,2690,2690,2700,2702,2702,2703,2703,2705,2706,2707,2707,2708,2710,2713,2718,2722,2728,2736,2738,2740,2747,2747,2750,2750,2750,2751,2754,2754,2755,2759,2759,2760,2760,2762,2765,2765,2766,2772,2776,2776,2777,2778,2778,2781,2783,2785,2786,2789,2789,2791,2792,2792,2793,2799,2799,2800,2800,2805,2807,2807,2808,2808,2808,2811,2811,2814,2820,2823,2824,2826,2826,2827,2829,2829,2829,2833,2835,2837,2838,2840,2841,2843,2843,2843,2844,2845,2849,2849,2849,2850,2851,2851,2851,2853,2853,2854,2855,2859,2861,2864,2867,2868,2871,2872,2873,2874,2877,2878,2880,2880,2881,2882,2882,2885,2893,2900,2900,2903,2904,2905,2907,2909,2910,2912,2914,2921,2923,2923,2924,2924,2925,2929,2934,2936,2942,2943,2943,2943,2949,2953,2954,2954,2954,2955,2956,2958,2959,2960,2962,2970,2974,2974,2978,2980,2988,2992,2992,2992,2993,2995,2997,3000,3005,3005,3007,3009,3010,3010,3010,3013,3014,3014,3016,3017,3019,3019,3020,3033,3038,3040,3042,3047,3048,3049,3052,3056,3057,3058,3060,3061,3061,3065,3070,3072,3075,3075,3077,3080,3081,3081,3082,3083,3083,3084,3085,3085,3085,3085,3089,3090,3092,3092,3094,3095,3095,3102,3109,3110,3111,3112,3115,3117,3121,3122,3123,3124,3125,3125,3125,3126,3129,3134,3138,3142,3143,3144,3145,3145,3147,3147,3148,3155,3155,3156,3160,3168,3174,3175,3175,3175,3179,3181,3182,3186,3188,3189,3189,3192,3195,3195,3198,3203,3205,3209,3214,3216,3218,3218,3221,3223,3223,3224,3225,3233,3233,3235,3237,3239,3239,3247,3249,3249,3252,3256,3257,3263,3265,3266,3267,3268,3275,3276,3277,3279,3281,3285,3286,3294,3297,3305,3308,3309,3309,3310,3311,3312,3312,3314,3319,3322,3323,3324,3324,3327,3327,3330,3331,3331,3332,3336,3337,3338,3345,3345,3346,3350,3351,3351,3351,3351,3353,3357,3358,3358,3358,3360,3364,3364,3364,3370,3371,3372,3372,3373,3374,3374,3384,3388,3389,3389,3391,3392,3392,3394,3398,3398,3400,3402,3407,3409,3413,3414,3421,3421,3423,3425,3427,3431,3433,3435,3436,3437,3444,3444,3446,3447,3447,3448,3450,3462,3469,3473,3477,3478,3484,3486,3488,3492,3494,3494,3495,3496,3497,3497,3503,3506,3507,3508,3510,3513,3515,3516,3517,3517,3523,3525,3525,3528,3529,3530,3530,3533,3535,3538,3539,3539,3540,3545,3545,3547,3549,3550,3550,3552,3553,3558,3558,3561,3562,3564,3577,3577,3577,3582,3584,3585,3588,3589,3592,3596,3600,3603,3604,3604,3605,3607,3608,3612,3613,3614,3616,3618,3622,3624,3624,3625,3627,3631,3631,3632,3632,3634,3636,3637,3638,3640,3640,3640,3644,3647,3647,3648,3648,3650,3651,3653,3653,3653,3655,3655,3656,3656,3660,3661,3661,3661,3662,3662,3663,3664,3665,3667,3669,3673,3675,3677,3677,3680,3684,3688,3690,3694,3696,3697,3698,3699,3702,3707,3707,3708,3710,3711,3713,3713,3716,3717,3717,3719,3719,3721,3723,3725,3726,3728,3733,3739,3740,3740,3746,3746,3750,3752,3753,3754,3754,3754,3756,3759,3760,3762,3765,3766,3769,3774,3775,3776,3778,3779,3779,3780,3782,3782,3785,3786,3789,3789,3791,3792,3792,3794,3797,3799,3799,3801,3802,3803,3806,3806,3807,3809,3809,3811,3814,3815,3818,3821,3824,3826,3827,3829,3831,3832,3834,3838,3840,3841,3841,3849,3853,3855,3856,3860,3861,3862,3862,3864,3865,3871,3873,3874,3878,3880,3881,3881,3884,3885,3886,3886,3891,3892,3892,3893,3894,3894,3896,3898,3899,3901,3904,3905,3906,3907,3911,3915,3916,3916,3918,3920,3922,3923,3924,3925,3927,3931,3932,3933,3935,3936,3937,3937,3937,3945,3947,3952,3953,3955,3955,3959,3963,3967,3967,3968,3972,3979,3981,3981,3981,3982,3985,3986,3992,3995,3999,3999,3999,4000,4002,4005,4005,4008,4012,4013,4013,4015,4018,4023,4024,4027,4031,4031,4033,4033,4033,4037,4041,4043,4044,4045,4046,4046,4047,4053,4053,4055,4056,4056,4057,4063,4063,4066,4069,4070,4070,4076,4077,4078,4083,4085,4087,4087,4087,4089,4092,4092,4092,4092,4095,4099,4100,4104,4104,4105,4108,4109,4109,4110,4115,4117,4117,4119,4120,4120,4121,4122,4124,4126,4127,4137,4142,4143,4144,4144,4144,4146,4147,4149,4149,4153,4156,4159,4160,4162,4162,4166,4166,4166,4169,4171,4172,4172,4175,4176,4177,4179,4179,4181,4184,4185,4185,4190,4194,4196,4200,4201,4204,4204,4206,4207,4209,4211,4211,4212,4213,4215,4216,4216,4219,4221,4225,4229,4233,4236,4238,4240,4245,4246,4248,4248,4250,4250,4250,4251,4255,4261,4264,4265,4265,4266,4268,4268,4270,4273,4278,4279,4284,4289,4295,4296,4297,4298,4298,4299,4302,4302,4308,4310,4312,4317,4318,4320,4322,4325,4327,4333,4335,4336,4337,4339,4342,4343,4348,4349,4350,4351,4354,4355,4357,4358,4359,4361,4361,4362,4362,4362,4363,4365,4367,4369,4376,4379,4380,4382,4384,4392,4394,4398,4401,4403,4404,4406,4409,4409,4412,4412,4415,4423,4427,4427,4433,4438,4439,4447,4448,4450,4451,4452,4453,4454,4455,4455,4457,4458,4459,4460,4460,4462,4464,4466,4471,4471,4472,4474,4474,4476,4478,4478,4479,4479,4480,4481,4483,4484,4486,4487,4488,4489,4491,4500,4502,4503,4506,4509,4510,4513,4518,4525,4525,4525,4526,4527,4529,4535,4538,4539,4544,4551,4551,4551,4560,4563,4566,4568,4569,4570,4574,4575,4577,4577,4579,4580,4580,4581,4584,4584,4585,4585,4588,4589,4592,4593,4595,4597,4598,4600,4604,4606,4608,4609,4609,4611,4613,4614,4616,4617,4618,4619,4619,4621,4622,4631,4632,4638,4640,4640,4643,4645,4650,4654,4654,4657,4659,4659,4660,4660,4664,4665,4666,4669,4673,4676,4677,4678,4678,4683,4684,4689,4695,4699,4701,4703,4705,4708,4708,4709,4710,4712,4713,4714,4714,4715,4715,4718,4718,4719,4719,4723,4725,4736,4741,4743,4745,4745,4746,4749,4751,4757,4757,4760,4760,4760,4761,4765,4766,4769,4776,4780,4782,4783,4791,4792,4793,4793,4795,4796,4798,4799,4799,4800,4803,4803,4807,4808,4814,4814,4816,4817,4819,4821,4824,4826,4827,4833,4833,4834,4839,4840,4840,4843,4845,4845,4852,4853,4854,4859,4860,4861,4862,4867,4869,4870,4870,4872,4872,4874,4876,4877,4877,4878,4885,4885,4886,4891,4891,4891,4892,4893,4895,4896,4898,4901,4902,4902,4908,4910,4910,4918,4919,4920,4922,4925,4928,4932,4935,4941,4943,4945,4947,4947,4958,4958,4960,4966,4967,4969,4970,4970,4970,4971,4971,4973,4975,4975,4976,4982,4983,4984,4987,4991,4991,4992,4995,4995,5000,5003,5007,5009,5010,5011,5016,5017,5018,5022,5026,5032,5034,5034,5035,5038,5041,5041,5041,5042,5054,5054,5058,5060,5060,5062,5064,5065,5070,5072,5075,5076,5077,5077,5082,5082,5087,5088,5090,5096,5096,5097,5097,5098,5099,5102,5107,5107,5110,5111,5114,5119,5119,5123,5126,5127,5129,5131,5131,5133,5134,5136,5136,5138,5140,5143,5143,5144,5146,5148,5149,5149,5151,5152,5153,5159,5163,5163,5164,5166,5178,5179,5180,5181,5182,5183,5186,5187,5188,5188,5189,5190,5190,5196,5197,5198,5200,5200,5203,5204,5205,5206,5208,5209,5209,5212,5216,5217,5221,5222,5224,5225,5227,5227,5227,5228,5228,5231,5232,5233,5233,5233,5233,5234,5244,5245,5246,5246,5248,5252,5254,5256,5256,5257,5258,5258,5259,5261,5262,5266,5269,5270,5272,5275,5275,5275,5279,5281,5284,5284,5284,5285,5286,5287,5288,5291,5292,5294,5295,5297,5299,5302,5303,5303,5308,5310,5312,5314,5320,5323,5323,5324,5326,5326,5327,5328,5329,5334,5336,5337,5338,5339,5340,5342,5344,5348,5349,5349,5353,5353,5362,5362,5366,5374,5377,5378,5384,5387,5388,5390,5390,5391,5391,5391,5399,5400,5404,5408,5414,5415,5418,5421,5422,5423,5423,5426,5426,5427,5428,5431,5432,5436,5437,5438,5439,5441,5442,5447,5448,5450,5450,5451,5452,5453,5454,5455,5456,5456,5457,5461,5462,5463,5465,5465,5467,5467,5469,5469,5470,5471,5471,5472,5473,5474,5475,5478,5480,5482,5482,5485,5485,5489,5491,5496,5496,5502,5505,5506,5511,5512,5514,5516,5519,5519,5525,5526,5528,5528,5529,5530,5533,5538,5545,5547,5547,5548,5550,5550,5556,5560,5565,5571,5572,5575,5578,5578,5578,5579,5588,5590,5591,5591,5593,5596,5596,5596,5597,5601,5607,5607,5608,5609,5611,5611,5613,5613,5613,5614,5621,5623,5626,5628,5628,5629,5630,5639,5639,5642,5642,5644,5644,5646,5647,5648,5649,5649,5654,5656,5657,5658,5659,5659,5659,5659,5661,5665,5666,5666,5672,5673,5674,5676,5676,5678,5679,5679,5681,5682,5682,5686,5686,5691,5692,5693,5694,5698,5699,5701,5706,5708,5708,5711,5715,5718,5720,5721,5722,5722,5725,5728,5728,5729,5731,5733,5733,5733,5735,5735,5735,5736,5739,5739,5740,5744,5745,5747,5748,5752,5752,5753,5754,5757,5758,5759,5764,5768,5770,5775,5777,5778,5781,5782,5783,5783,5786,5787,5788,5793,5793,5796,5796,5797,5797,5800,5803,5806,5811,5813,5813,5815,5818,5820,5821,5822,5823,5825,5826,5827,5829,5832,5833,5835,5835,5837,5838,5838,5841,5843,5843,5844,5848,5848,5849,5850,5851,5854,5857,5858,5860,5860,5861,5861,5862,5863,5867,5868,5869,5873,5882,5883,5884,5886,5887,5888,5889,5889,5891,5895,5897,5898,5902,5904,5905,5907,5911,5912,5912,5913,5917,5918,5926,5929,5930,5932,5932,5933,5935,5938,5939,5941,5941,5941,5941,5942,5943,5952,5953,5953,5956,5956,5959,5961,5961,5968,5970,5975,5976,5976,5979,5980,5981,5982,5982,5983,5983,5985,5986,5986,5987,5988,5989,5992,5999,6000,6001,6002,6002,6007,6010,6012,6012,6013,6016,6018,6019,6019,6020,6022,6022,6024,6026,6028,6029,6035,6035,6040,6041,6043,6047,6050,6051,6053,6054,6054,6060,6061,6066,6070,6070,6072,6077,6078,6078,6079,6079,6080,6080,6082,6082,6090,6091,6092,6093,6096,6099,6099,6101,6102,6102,6105,6110,6115,6116,6126,6127,6127,6129,6130,6132,6133,6134,6135,6140,6141,6141,6142,6143,6143,6146,6146,6148,6148,6151,6154,6157,6159,6159,6161,6162,6162,6167,6168,6168,6169,6170,6172,6172,6172,6172,6174,6175,6178,6178,6178,6183,6185,6191,6195,6197,6198,6199,6200,6202,6202,6203,6204,6208,6209,6210,6211,6215,6215,6216,6216,6216,6219,6222,6224,6226,6228,6230,6233,6237,6240,6241,6243,6244,6247,6248,6249,6250,6254,6259,6260,6260,6266,6270,6271,6271,6271,6271,6271,6272,6274,6276,6276,6280,6281,6284,6285,6289,6290,6293,6294,6295,6295,6295,6298,6299,6306,6309,6311,6313,6314,6317,6320,6322,6324,6324,6325,6330,6331,6335,6336,6339,6340,6345,6346,6346,6346,6351,6352,6355,6355,6359,6362,6366,6367,6367,6369,6376,6377,6380,6380,6380,6389,6392,6392,6392,6392,6394,6396,6400,6402,6407,6412,6413,6414,6417,6418,6418,6419,6421,6425,6426,6430,6431,6433,6433,6433,6434,6435,6435,6439,6441,6444,6444,6446,6446,6453,6453,6454,6456,6458,6459,6460,6461,6462,6463,6463,6465,6466,6469,6471,6471,6472,6479,6481,6481,6482,6485,6486,6492,6494,6498,6499,6502,6502,6502,6503,6505,6507,6510,6510,6511,6514,6515,6515,6515,6516,6519,6521,6522,6524,6525,6526,6531,6534,6536,6537,6541,6543,6544,6547,6549,6552,6553,6555,6556,6557,6558,6558,6558,6559,6561,6564,6567,6570,6570,6572,6574,6576,6578,6581,6582,6583,6583,6584,6585,6585,6586,6588,6590,6591,6591,6593,6596,6599,6601,6603,6605,6605,6608,6608,6608,6612,6613,6613,6615,6615,6619,6621,6622,6625,6627,6628,6630,6631,6635,6636,6640,6641,6642,6642,6643,6646,6647,6650,6653,6660,6660,6662,6665,6665,6666,6669,6671,6671,6675,6676,6680,6681,6683,6684,6685,6687,6687,6687,6688,6688,6690,6692,6694,6697,6698,6702,6704,6706,6714,6714,6718,6728,6740,6741,6742,6745,6751,6752,6757,6759,6759,6760,6760,6767,6772,6774,6774,6777,6778,6779,6781,6783,6784,6787,6790,6791,6792,6793,6797,6798,6800,6800,6801,6808,6809,6810,6810,6810,6811,6811,6811,6812,6814,6815,6817,6820,6821,6822,6823,6824,6825,6826,6826,6830,6833,6835,6836,6838,6838,6839,6839,6842,6844,6847,6851,6851,6857,6859,6862,6863,6864,6867,6867,6867,6869,6869,6869,6869,6871,6871,6874,6875,6876,6880,6881,6881,6882,6883,6885,6892,6897,6899,6903,6903,6904,6904,6904,6904,6906,6908,6908,6908,6910,6913,6915,6917,6920,6920,6924,6927,6933,6934,6935,6936,6936,6936,6937,6939,6941,6942,6942,6943,6948,6952,6952,6953,6956,6956,6958,6959,6961,6962,6963,6964,6964,6965,6966,6970,6972,6973,6976,6977,6978,6981,6987,6990,6993,6993,6998,7009,7009,7010,7012,7017,7023,7028,7029,7030,7030,7031,7034,7036,7037,7038,7042,7045,7049,7051,7052,7052,7057,7060,7061,7062,7063,7064,7064,7065,7066,7070,7074,7078,7079,7080,7082,7082,7084,7087,7091,7092,7094,7095,7099,7099,7100,7100,7103,7106,7111,7119,7121,7122,7127,7128,7133,7134,7134,7136,7139,7140,7141,7143,7143,7143,7148,7148,7154,7162,7162,7173,7175,7178,7178,7180,7181,7182,7184,7185,7190,7190,7191,7191,7192,7194,7195,7197,7198,7198,7198,7199,7200,7205,7209,7209,7211,7212,7213,7216,7217,7222,7224,7227,7228,7229,7237,7238,7241,7243,7244,7245,7247,7247,7248,7249,7252,7255,7257,7262,7263,7273,7274,7276,7276,7277,7281,7282,7283,7283,7285,7287,7287,7288,7288,7293,7294,7296,7300,7303,7308,7310,7311,7313,7316,7317,7318,7325,7326,7326,7328,7329,7331,7332,7333,7335,7335,7336,7337,7341,7341,7342,7343,7343,7344,7346,7347,7348,7350,7352,7355,7357,7357,7360,7361,7365,7365,7367,7369,7369,7370,7376,7379,7379,7381,7383,7391,7392,7393,7395,7395,7399,7401,7401,7401,7401,7403,7403,7404,7404,7414,7414,7419,7421,7430,7432,7433,7435,7436,7436,7441,7441,7445,7447,7448,7448,7448,7449,7449,7449,7450,7450,7451,7452,7454,7454,7454,7456,7456,7457,7460,7461,7462,7463,7464,7465,7465,7469,7473,7474,7474,7475,7475,7478,7480,7482,7486,7487,7494,7495,7496,7497,7497,7497,7499,7504,7510,7511,7512,7524,7524,7526,7527,7528,7528,7529,7532,7534,7536,7538,7541,7544,7546,7546,7552,7552,7555,7555,7559,7569,7572,7574,7574,7577,7578,7578,7579,7579,7580,7580,7585,7592,7594,7594,7597,7601,7603,7614,7615,7616,7616,7617,7618,7620,7622,7623,7624,7628,7629,7630,7631,7631,7631,7632,7635,7636,7637,7639,7639,7640,7640,7640,7643,7645,7651,7653,7655,7656,7657,7658,7659,7660,7663,7667,7669,7671,7673,7676,7678,7679,7684,7685,7686,7687,7688,7688,7689,7690,7690,7695,7697,7705,7706,7708,7710,7715,7719,7721,7726,7729,7730,7731,7735,7737,7740,7742,7744,7745,7748,7749,7750,7754,7757,7757,7758,7762,7763,7763,7765,7765,7767,7768,7769,7774,7776,7776,7780,7781,7784,7784,7785,7786,7788,7789,7790,7791,7791,7794,7794,7804,7805,7805,7806,7808,7810,7812,7814,7815,7815,7817,7820,7833,7834,7835,7836,7840,7843,7846,7848,7850,7851,7852,7857,7864,7864,7865,7865,7865,7865,7865,7865,7868,7868,7871,7872,7874,7877,7878,7880,7882,7885,7885,7886,7888,7894,7895,7895,7895,7896,7900,7901,7902,7904,7904,7905,7907,7910,7910,7911,7913,7914,7915,7920,7921,7923,7923,7923,7923,7924,7931,7931,7931,7932,7936,7938,7938,7939,7944,7946,7946,7947,7947,7951,7951,7954,7955,7960,7960,7962,7965,7973,7975,7975,7977,7978,7979,7981,7984,7985,7985,7985,7986,7990,7992,7992,7993,7995,8002,8003,8004,8004,8004,8006,8014,8015,8018,8018,8020,8022,8022,8023,8024,8024,8025,8025,8025,8029,8029,8031,8031,8034,8034,8035,8036,8040,8040,8044,8044,8044,8046,8046,8049,8051,8051,8052,8052,8058,8060,8064,8064,8065,8066,8068,8070,8072,8072,8072,8072,8075,8077,8077,8079,8080,8080,8081,8086,8088,8088,8088,8090,8091,8092,8093,8095,8095,8098,8100,8102,8106,8114,8115,8116,8117,8119,8120,8121,8122,8124,8125,8127,8129,8132,8133,8133,8139,8140,8141,8147,8150,8152,8153,8154,8156,8163,8164,8168,8168,8169,8169,8170,8170,8171,8171,8171,8173,8175,8183,8183,8189,8189,8190,8193,8193,8197,8197,8198,8199,8199,8202,8206,8207,8208,8208,8208,8209,8209,8210,8215,8216,8217,8218,8219,8222,8224,8225,8225,8226,8228,8228,8230,8234,8237,8242,8243,8245,8245,8246,8247,8248,8248,8257,8258,8259,8260,8261,8262,8266,8267,8267,8269,8274,8277,8277,8278,8283,8290,8293,8298,8305,8305,8306,8307,8310,8311,8311,8312,8313,8321,8324,8326,8327,8328,8328,8328,8330,8331,8331,8332,8332,8333,8333,8333,8333,8336,8338,8339,8341,8342,8343,8344,8344,8346,8348,8349,8356,8359,8362,8362,8364,8365,8365,8366,8370,8370,8373,8374,8376,8379,8385,8386,8387,8388,8389,8394,8395,8396,8397,8398,8399,8400,8400,8403,8413,8414,8414,8416,8418,8426,8429,8429,8429,8432,8435,8435,8438,8439,8442,8442,8443,8446,8446,8447,8449,8452,8452,8454,8455,8458,8459,8461,8461,8461,8461,8463,8465,8472,8475,8483,8485,8489,8489,8490,8494,8497,8497,8505,8507,8508,8509,8515,8517,8518,8526,8527,8527,8528,8533,8536,8541,8545,8546,8552,8552,8553,8555,8556,8556,8556,8561,8564,8567,8569,8570,8571,8572,8573,8573,8574,8575,8576,8577,8579,8579,8579,8580,8584,8585,8586,8588,8590,8594,8596,8598,8600,8603,8603,8604,8604,8604,8605,8607,8608,8612,8616,8622,8624,8624,8624,8625,8629,8632,8635,8636,8643,8644,8650,8656,8657,8658,8659,8661,8662,8665,8666,8668,8670,8674,8674,8675,8675,8682,8683,9015,9015,9012,9011,9011,9009,9008,9002,9001,9001,9000,8999,8997,8996,8995,8991,8990,8990,8988,8984,8980,8979,8974,8973,8973,8969,8968,8967,8966,8966,8964,8962,8959,8958,8955,8954,8954,8953,8950,8948,8946,8937,8936,8932,8929,8928,8927,8925,8925,8919,8909,8909,8905,8902,8899,8896,8891,8888,8888,8886,8886,8886,8880,8877,8877,8874,8872,8870,8863,8862,8859,8859,8856,8855,8855,8855,8855,8853,8852,8848,8847,8847,8847,8842,8840,8840,8836,8836,8834,8832,8832,8831,8826,8826,8825,8823,8820,8819,8818,8818,8817,8817,8812,8811,8811,8810,8809,8807,8806,8802,8802,8800,8800,8798,8795,8790,8787,8786,8786,8784,8783,8783,8783,8781,8780,8780,8777,8772,8769,8768,8768,8767,8765,8764,8762,8760,8756,8754,8752,8752,8751,8751,8751,8750,8750,8747,8746,8746,8739,8739,8738,8737,8735,8734,8732,8730,8728,8728,8727,8725,8723,8719,8717,8714,8713,8711,8709,8708,8705,8705,8704,8704,8701,8700,8700,8697,8695,8694,8692,8688,8687,8687,8686,8686,8684,8684,9016,9016,9021,9022,9025,9029,9032,9033,9036,9039,9040,9043,9049,9052,9052,9052,9053,9059,9060,9061,9062,9067,9075,9075,9081,9081,9082,9084,9088,9089,9090,9091,9092,9092,9094,9094,9101,9103,9104,9108,9109,9114,9115,9116,9116,9116,9118,9120,9124,9125,9125,9125,9126,9128,9130,9131,9131,9132,9132,9141,9146,9146,9147,9150,9155,9155,9156,9159,9160,9161,9162,9169,9170,9172,9175,9178,9180,9185,9185,9186,9190,9193,9193,9194,9199,9203,9204,9209,9213,9215,9218,9221,9223,9223,9226,9229,9229,9232,9233,9234,9237,9238,9239,9240,9242,9244,9245,9245,9252,9252,9253,9255,9259,9261,9266,9267,9269,9272,9274,9277,9277,9278,9279,9280,9281,9282,9283,9286,9287,9287,9291,9292,9292,9296,9302,9307,9307,9308,9308,9312,9312,9317,9318,9323,9325,9325,9326,9328,9328,9329,9331,9336,9336,9338,9346,9349,9349,9349,9352,9354,9355,9356,9360,9361,9361,9361,9363,9363,9364,9368,9369,9372,9373,9378,9380,9380,9383,9383,9383,9388,9389,9390,9393,9395,9396,9397,9398,9400,9400,9404,9407,9407,9409,9413,9415,9415,9415,9416,9419,9420,9423,9423,9424,9425,9425,9427,9427,9429,9429,9430,9430,9432,9433,9435,9436,9441,9442,9443,9444,9444,9447,9447,9448,9452,9453,9458,9461,9462,9463,9463,9465,9468,9469,9470,9472,9473,9473,9473,9474,9476,9477,9480,9482,9485,9486,9493,9495,9497,9498,9500,9501,9502,9502,9503,9508,9509,9509,9513,9515,9518,9524,9526,9528,9532,9533,9533,9535,9536,9539,9540,9541,9544,9545,9546,9546,9547,9547,9548,9548,9551,9553,9555,9558,9559,9559,9562,9563,9566,9570,9571,9572,9573,9573,9577,9582,9583,9584,9584,9589,9590,9594,9596,9596,9598,9601,9601,9602,9605,9606,9607,9608,9609,9610,9612,9617,9618,9619,9620,9623,9627,9627,9636,9638,9639,9639,9640,9642,9642,9643,9649,9655,9656,9656,9659,9660,9660,9663,9668,9669,9671,9675,9676,9678,9680,9680,9680,9681,9682,9689,9690,9695,9695,9699,9699,9699,9702,9704,9704,9705,9707,9707,9707,9708,9708,9710,9711,9712,9714,9719,9725,9727,9727,9728,9730,9733,9734,9739,9740,9743,9744,9744,9748,9750,9756,9758,9759,9760,9761,9765,9765,9766,9768,9770,9782,9784,9787,9791,9796,9796,9797,9799,9800,9802,9803,9804,9804,9805,9805,9807,9808,9809,9809,9813,9816,9820,9821,9822,9823,9823,9825,9827,9829,9829,9830,9832,9834,9835,9837,9842,9845,9848,9849,9851,9853,9855,9855,9858,9858,9862,9864,9866,9866,9867,9867,9872,9873,9876,9880,9882,9882,9885,9886,9887,9890,9895,9896,9898,9899,9902,9902,9903,9907,9909,9921,9931,9931,9932,9937,9941,9941,9944,9947,9947,9947,9948,9953,9954,9954,9957,9966,9966,9969,9969,9971,9971,9972,9976,9979,9982,9984,9984,9984,9984,9986,9987,9999,10000,10001,10002,10008,10010,10014,10018,10019,10023,10027,10034,10036,10037,10041,10041,10041,10043,10044,10045,10050,10051,10051,10051,10051,10052,10052,10053,10054,10056,10058,10058,10058,10059,10059,10064,10066,10068,10068,10070,10070,10071,10073,10081,10081,10082,10083,10087,10090,10092,10093,10093,10094,10095,10097,10097,10099,10100,10101,10105,10105,10108,10111,10112,10117,10117,10120,10121,10122,10124,10126,10126,10128,10131,10132,10136,10137,10140,10141,10142,10146,10147,10147,10147,10150,10154,10156,10156,10160,10163,10164,10164,10165,10167,10168,10168,10169,10169,10171,10172,10174,10176,10176,10178,10179,10181,10182,10182,10188,10191,10193,10195,10195,10200,10200,10202,10203,10208,10215,10215,10216,10219,10223,10225,10228,10228,10232,10233,10234,10235,10238,10244,10245,10246,10247,10248,10251,10253,10254,10254,10256,10262,10263,10270,10271,10272,10273,10275,10275,10281,10284,10284,10284,10285,10285,10291,10297,10297,10298,10300,10302,10304,10306,10306,10307,10309,10312,10312,10313,10313,10314,10315,10321,10323,10325,10327,10329,10331,10333,10337,10338,10338,10339,10343,10344,10346,10348,10348,10352,10353,10357,10357,10358,10362,10366,10367,10370,10370,10371,10372,10377,10377,10377,10381,10382,10382,10383,10385,10387,10388,10390,10391,10391,10391,10392,10393,10395,10397,10399,10409,10412,10413,10414,10414,10417,10417,10420,10420,10423,10425,10428,10429,10431,10434,10435,10437,10440,10441,10443,10443,10444,10444,10444,10446,10449,10450,10450,10451,10452,10455,10459,10461,10463,10468,10471,10474,10475,10475,10478,10483,10483,10491,10492,10499,10499,10499,10502,10504,10510,10510,10510,10510,10515,10518,10519,10520,10526,10529,10533,10533,10539,10540,10540,10545,10547,10548,10550,10552,10554,10555,10555,10555,10556,10557,10562,10563,10564,10565,10567,10570,10571,10572,10573,10578,10580,10580,10583,10583,10588,10592,10593,10595,10598,10600,10603,10603,10605,10606,10608,10610,10610,10610,10614,10615,10615,10617,10618,10620,10620,10621,10621,10624,10626,10628,10628,10632,10638,10640,10646,10648,10649,10650,10651,10652,10652,10653,10654,10658,10663,10664,10665,10668,10669,10670,10672,10672,10674,10677,10682,10684,10686,10694,10700,10702,10709,10710,10711,10711,10713,10714,10716,10721,10722,10722,10722,10722,10723,10724,10730,10730,10731,10733,10734,10738,10740,10744,10753,10756,10759,10760,10761,10763,10765,10767,10771,10773,10778,10780,10780,10781,10792,10792,10799,10799,10799,10800,10808,10811,10812,10813,10813,10815,10816,10816,10816,10818,10820,10821,10824,10824,10825,10827,10828,10829,10830,10831,10833,10834,10836,10837,10837,10840,10842,10842,10842,10845,10848,10855,10857,10861,10866,10867,10867,10867,10868,10872,10878,10880,10881,10883,10887,10888,10889,10892,10893,10896,10898,10898,10900,10902,10902,10904,10904,10910,10911,10913,10920,10923,10927,10930,10930,10931,10932,10935,10937,10940,10945,10949,10953,10954,10955,10961,10962,10967,10971,10971,10972,10973,10974,10974,10974,10975,10981,10983,10984,10984,10986,10987,10988,10988,10988,10989,10990,10992,10994,10994,10996,10999,11000,11004,11006,11010,11012,11012,11013,11021,11022,11022,11022,11023,11024,11026,11029,11030,11032,11036,11037,11037,11040,11042,11044,11049,11049,11051,11053,11056,11059,11061,11063,11064,11065,11065,11069,11070,11070,11077,11078,11079,11081,11081,11084,11085,11091,11092,11092,11093,11101,11103,11104,11105,11112,11115,11117,11120,11121,11121,11122,11123,11127,11130,11131,11131,11133,11136,11137,11138,11142,11144,11151,11151,11154,11155,11156,11157,11158,11158,11161,11163,11165,11165,11166,11168,11170,11170,11173,11174,11174,11185,11186,11187,11193,11198,11199,11200,11200,11200,11202,11204,11208,11209,11209,11209,11210,11211,11211,11213,11215,11216,11224,11226,11229,11231,11232,11234,11235,11235,11236,11236,11237,11243,11243,11251,11256,11257,11261,11261,11261,11265,11266,11267,11268,11271,11273,11273,11278,11280,11284,11286,11289,11289,11292,11293,11293,11294,11294,11295,11297,11300,11302,11304,11305,11306,11307,11307,11307,11308,11309,11309,11309,11313,11315,11316,11319,11320,11324,11332,11334,11335,11336,11338,11339,11340,11341,11342,11343,11343,11346,11350,11353,11355,11355,11355,11357,11357,11361,11362,11363,11363,11363,11373,11374,11374,11375,11375,11377,11378,11379,11381,11391,11392,11393,11394,11396,11397,11398,11400,11403,11405,11406,11409,11410,11410,11411,11415,11416,11418,11418,11418,11419,11419,11423,11430,11431,11431,11432,11433,11434,11438,11439,11440,11440,11440,11441,11442,11443,11444,11449,11449,11451,11455,11456,11457,11459,11460,11466,11467,11469,11469,11470,11471,11471,11477,11477,11478,11479,11482,11482,11482,11482,11483,11491,11491,11491,11492,11495,11496,11497,11497,11497,11499,11502,11503,11503,11504,11506,11507,11512,11512,11516,11527,11527,11528,11530,11534,11538,11538,11539,11541,11546,11547,11548,11549,11551,11553,11553,11561,11566,11574,11574,11575,11577,11577,11578,11579,11580,11584,11586,11588,11590,11590,11590,11591,11593,11594,11598,11598,11605,11605,11606,11607,11607,11608,11608,11613,11618,11619,11620,11620,11623,11624,11631,11633,11635,11637,11637,11638,11639,11642,11644,11654,11658,11660,11662,11664,11664,11666,11666,11666,11667,11667,11668,11669,11669,11670,11670,11671,11673,11673,11677,11677,11678,11678,11679,11680,11681,11682,11682,11683,11689,11690,11691,11691,11692,11693,11696,11696,11696,11697,11701,11703,11704,11705,11710,11711,11713,11714,11714,11719,11719,11723,11725,11725,11727,11727,11729,11730,11731,11732,11735,11736,11740,11742,11743,11743,11748,11749,11750,11751,11751,11752,11754,11755,11756,11756,11757,11758,11759,11764,11766,11766,11768,11770,11774,11775,11776,11792,11792,11796,11800,11802,11808,11808,11809,11810,11810,11810,11813,11815,11823,11824,11825,11825,11832,11833,11835,11840,11840,11843,11844,11845,11848,11853,11853,11856,11857,11858,11858,11860,11862,11868,11872,11876,11881,11882,11884,11884,11887,11889,11889,11891,11898,11904,11905,11908,11908,11912,11913,11914,11914,11917,11920,11921,11922,11925,11926,11929,11929,11930,11932,11933,11933,11933,11935,11936,11939,11941,11943,11947,11947,11956,11956,11958,11960,11962,11963,11968,11971,11973,11974,11979,11981,11983,11990,11996,11997,12000,12000,12004,12005,12008,12011,12012,12012,12013,12020,12022,12026,12032,12033,12034,12036,12036,12037,12037,12039,12041,12042,12043,12054,12057,12058,12059,12060,12063,12065,12065,12065,12068,12071,12073,12073,12077,12077,12078,12079,12080,12080,12085,12086,12089,12093,12098,12102,12102,12109,12109,12109,12117,12118,12122,12125,12125,12126,12126,12130,12132,12133,12137,12139,12139,12139,12139,12140,12140,12141,12142,12142,12145,12148,12149,12150,12151,12152,12152,12153,12153,12154,12154,12157,12160,12165,12166,12169,12169,12170,12172,12174,12176,12189,12190,12190,12191,12193,12196,12197,12199,12202,12203,12203,12204,12204,12205,12205,12207,12210,12210,12210,12214,12215,12216,12216,12218,12218,12219,12221,12229,12230,12231,12234,12236,12237,12238,12238,12241,12242,12244,12251,12253,12255,12256,12256,12257,12258,12262,12263,12264,12267,12268,12270,12272,12273,12277,12277,12278,12279,12284,12285,12287,12287,12291,12294,12296,12296,12297,12301,12303,12308,12310,12310,12311,12317,12318,12319,12323,12323,12328,12329,12331,12333,12337,12342,12345,12346,12347,12349,12350,12350,12352,12352,12354,12357,12362,12364,12365,12366,12367,12372,12383,12383,12384,12388,12401,12402,12404,12404,12409,12411,12415,12417,12422,12428,12429,12430,12430,12430,12431,12432,12435,12437,12437,12445,12446,12448,12452,12453,12453,12454,12455,12455,12461,12462,12463,12466,12467,12470,12471,12477,12478,12479,12486,12495,12495,12496,12498,12503,12503,12504,12505,12505,12506,12509,12512,12514,12515,12521,12522,12522,12523,12524,12524,12525,12526,12526,12527,12528,12534,12534,12539,12540,12540,12543,12543,12544,12545,12546,12547,12547,12548,12549,12550,12552,12553,12554,12554,12558,12559,12560,12560,12564,12566,12568,12573,12574,12575,12575,12577,12578,12580,12586,12587,12589,12590,12591,12596,12596,12597,12597,12602,12604,12607,12607,12609,12609,12609,12613,12614,12623,12624,12625,12625,12627,12630,12630,12633,12634,12634,12635,12635,12639,12643,12645,12645,12647,12648,12650,12652,12652,12653,12655,12655,12657,12657,12657,12659,12660,12660,12661,12662,12662,12663,12666,12667,12668,12668,12677,12678,12678,12679,12679,12680,12680,12681,12681,12683,12691,12691,12692,12693,12693,12693,12693,12697,12700,12703,12706,12707,12717,12718,12723,12723,12726,12731,12738,12741,12745,12746,12750,12760,12762,12763,12770,12771,12774,12774,12774,12774,12776,12777,12778,12780,12782,12782,12791,12794,12797,12798,12799,12800,12802,12806,12806,12807,12807,12810,12811,12812,12813,12818,12819,12820,12824,12828,12828,12833,12834,12836,12836,12837,12842,12845,12845,12845,12846,12847,12852,12855,12859,12865,12868,12870,12870,12876,12876,12877,12878,12882,12884,12884,12887,12887,12887,12901,12901,12902,12904,12909,12910,12916,12916,12917,12917,12923,12927,12928,12930,12933,12933,12934,12934,12935,12935,12943,12943,12946,12947,12949,12954,12955,12957,12958,12961,12962,12963,12963,12964,12967,12973,12975,12975,12976,12978,12979,12984,12989,12989,12992,12994,12994,12994,12997,12998,13001,13003,13003,13007,13010,13015,13018,13019,13026,13027,13033,13034,13036,13039,13040,13041,13043,13044,13046,13048,13048,13058,13060,13065,13066,13068,13070,13071,13071,13071,13073,13075,13076,13077,13078,13082,13083,13085,13086,13089,13090,13095,13095,13098,13100,13105,13107,13110,13110,13111,13112,13113,13115,13117,13120,13120,13120,13122,13123,13124,13125,13127,13135,13139,13141,13141,13144,13149,13151,13151,13156,13159,13161,13161,13164,13168,13172,13175,13176,13179,13179,13179,13181,13183,13183,13186,13188,13190,13193,13194,13196,13198,13201,13201,13206,13206,13208,13209,13210,13211,13211,13215,13216,13217,13219,13223,13228,13228,13230,13230,13233,13235,13236,13238,13240,13240,13242,13243,13244,13245,13245,13247,13256,13257,13259,13261,13262,13266,13267,13268,13270,13271,13272,13272,13277,13278,13279,13279,13281,13283,13283,13283,13287,13288,13290,13292,13294,13296,13297,13301,13301,13302,13303,13309,13310,13311,13312,13312,13314,13316,13319,13319,13319,13320,13327,13327,13330,13333,13335,13339,13340,13340,13341,13350,13350,13355,13357,13357,13363,13365,13369,13371,13372,13374,13376,13376,13379,13379,13379,13381,13383,13392,13392,13400,13402,13402,13406,13416,13417,13418,13418,13423,13425,13430,13433,13434,13436,13436,13438,13445,13446,13446,13450,13450,13451,13452,13452,13452,13454,13455,13459,13463,13464,13464,13465,13465,13467,13469,13471,13472,13473,13476,13477,13479,13483,13488,13488,13503,13505,13505,13508,13510,13511,13511,13511,13512,13514,13517,13517,13517,13519,13519,13520,13523,13523,13525,13526,13532,13532,13533,13536,13539,13541,13541,13541,13542,13546,13549,13549,13551,13551,13553,13554,13558,13558,13558,13560,13562,13571,13572,13574,13581,13582,13583,13583,13588,13588,13589,13591,13592,13592,13599,13600,13602,13605,13606,13608,13610,13612,13612,13615,13616,13616,13616,13617,13635,13637,13638,13639,13643,13644,13648,13649,13652,13653,13654,13657,13663,13665,13666,13670,13674,13676,13677,13677,13679,13681,13682,13682,13685,13693,13693,13697,13698,13699,13700,13702,13709,13710,13710,13711,13713,13719,13719,13721,13722,13726,13727,13729,13730,13730,13731,13731,13732,13737,13741,13744,13746,13747,13749,13750,13753,13754,13755,13758,13758,13760,13760,13761,13761,13762,13762,13764,13774,13776,13780,13782,13783,13790,13791,13791,13791,13792,13793,13794,13796,13796,13796,13798,13799,13800,13802,13804,13810,13810,13813,13813,13817,13821,13826,13827,13827,13829,13832,13834,13834,13834,13836,13842,13844,13846,13848,13848,13849,13851,13852,13859,13860,13869,13870,13876,13878,13878,13878,13884,13886,13887,13888,13889,13893,13896,13898,13898,13904,13904,13914,13915,13915,13915,13925,13925,13926,13928,13929,13934,13934,13935,13938,13940,13945,13945,13945,13947,13948,13950,13952,13952,13954,13956,13957,13960,13965,13971,13972,13978,13979,13979,13983,13987,13989,13989,13994,13994,13996,13996,13998,14001,14001,14003,14004,14006,14007,14009,14010,14011,14011,14013,14016,14017,14018,14021,14022,14030,14032,14032,14032,14035,14036,14036,14036,14039,14039,14049,14050,14051,14052,14053,14054,14056,14058,14058,14061,14066,14066,14068,14069,14069,14076,14076,14080,14080,14086,14089,14091,14094,14096,14097,14097,14098,14099,14102,14105,14106,14107,14108,14109,14109,14110,14110,14114,14117,14119,14122,14123,14124,14131,14141,14142,14143,14145,14146,14147,14148,14149,14156,14157,14159,14159,14162,14165,14165,14166,14167,14171,14173,14174,14176,14177,14177,14178,14181,14182,14186,14188,14190,14192,14193,14198,14199,14199,14200,14201,14207,14208,14215,14216,14216,14217,14219,14223,14225,14225,14226,14227,14229,14229,14234,14236,14237,14239,14240,14241,14242,14244,14246,14247,14247,14249,14253,14253,14260,14260,14261,14263,14267,14269,14274,14274,14277,14277,14279,14280,14285,14287,14288,14288,14288,14289,14290,14300,14302,14303,14305,14307,14310,14310,14315,14315,14315,14316,14319,14320,14321,14322,14323,14329,14332,14334,14334,14342,14343,14349,14349,14352,14354,14358,14359,14360,14362,14364,14364,14364,14367,14368,14369,14370,14370,14371,14371,14375,14375,14376,14376,14380,14380,14380,14382,14384,14390,14390,14392,14392,14394,14396,14398,14401,14404,14406,14407,14412,14412,14412,14415,14416,14416,14416,14417,14423,14425,14425,14431,14434,14439,14447,14449,14454,14455,14455,14456,14457,14457,14458,14458,14463,14465,14465,14467,14468,14474,14480,14481,14485,14489,14494,14497,14499,14504,14508,14510,14511,14512,14513,14514,14515,14518,14519,14519,14523,14526,14527,14527,14529,14530,14530,14535,14536,14536,14538,14539,14539,14542,14544,14544,14545,14550,14552,14552,14552,14559,14559,14560,14563,14565,14567,14568,14569,14569,14573,14573,14574,14576,14576,14578,14578,14579,14585,14587,14587,14590,14593,14593,14599,14600,14601,14608,14612,14617,14619,14620,14622,14628,14628,14630,14631,14631,14634,14634,14636,14637,14639,14641,14642,14644,14646,14647,14647,14649,14653,14654,14656,14658,14658,14659,14660,14660,14661,14662,14662,14663,14664,14667,14672,14673,14677,14679,14680,14683,14684,14684,14687,14689,14690,14693,14702,14705,14706,14709,14710,14710,14711,14716,14716,14716,14717,14724,14730,14730,14731,14731,14732,14732,14734,14734,14735,14735,14737,14738,14738,14739,14740,14743,14745,14748,14749,14749,14750,14751,14752,14754,14754,14755,14759,14763,14763,14766,14768,14770,14771,14773,14776,14777,14784,14788,14790,14791,14792,14793,14794,14797,14798,14799,14800,14803,14805,14806,14812,14813,14819,14819,14819,14821,14824,14824,14827,14828,14828,14829,14830,14830,14830,14830,14834,14834,14846,14853,14854,14854,14855,14860,14876,14877,14877,14879,14881,14883,14883,14884,14887,14889,14895,14896,14897,14898,14905,14906,14908,14910,14911,14912,14913,14913,14920,14922,14924,14925,14927,14927,14929,14930,14930,14932,14932,14937,14941,14941,14942,14944,14946,14949,14954,14954,14955,14955,14955,14959,14959,14960,14960,14962,14962,14962,14962,14964,14966,14966,14969,14971,14971,14974,14975,14979,14979,14981,14982,14983,14984,14984,14986,14986,14988,14989,14992,14996,14999,15001,15007,15007,15010,15011,15011,15011,15012,15012,15015,15022,15023,15024,15025,15030,15031,15031,15032,15035,15036,15037,15039,15040,15043,15049,15050,15051,15055,15057,15058,15058,15059,15061,15062,15066,15068,15072,15072,15073,15073,15074,15074,15075,15076,15080,15080,15082,15086,15090,15093,15094,15097,15101,15101,15105,15105,15106,15107,15108,15108,15108,15110,15112,15113,15114,15116,15117,15118,15119,15121,15125,15125,15126,15126,15136,15140,15140,15144,15149,15150,15150,15153,15154,15155,15159,15160,15160,15164,15165,15165,15168,15168,15170,15171,15171,15173,15176,15177,15181,15181,15182,15184,15185,15187,15188,15190,15190,15190,15198,15199,15199,15202,15205,15206,15208,15212,15217,15220,15220,15221,15223,15224,15227,15228,15233,15234,15234,15236,15241,15241,15244,15245,15247,15247,15248,15249,15249,15252,15256,15258,15259,15260,15262,15263,15265,15268,15269,15276,15279,15279,15281,15282,15285,15286,15287,15290,15291,15293,15293,15297,15301,15302,15302,15303,15304,15305,15305,15311,15314,15322,15324,15328,15328,15330,15333,15336,15338,15338,15340,15342,15345,15347,15355,15363,15365,15367,15367,15371,15372,15372,15373,15374,15376,15376,15377,15379,15383,15384,15386,15387,15388,15390,15391,15394,15396,15400,15405,15405,15406,15410,15410,15413,15415,15415,15417,15424,15425,15434,15435,15435,15435,15440,15444,15445,15446,15447,15449,15450,15452,15453,15455,15456,15459,15460,15468,15470,15470,15471,15476,15478,15490,15491,15491,15492,15501,15501,15502,15502,15504,15506,15507,15508,15511,15512,15513,15515,15519,15520,15521,15522,15523,15524,15524,15527,15530,15531,15532,15533,15535,15536,15538,15539,15542,15542,15548,15551,15551,15555,15557,15557,15562,15563,15565,15567,15567,15567,15568,15569,15570,15571,15575,15575,15577,15577,15578,15579,15580,15581,15583,15584,15588,15590,15591,15592,15593,15595,15596,15600,15601,15603,15606,15606,15607,15611,15612,15614,15616,15618,15622,15623,15623,15627,15629,15631,15631,15639,15639,15641,15642,15643,15643,15645,15645,15647,15649,15655,15657,15658,15658,15658,15662,15664,15664,15665,15667,15669,15671,15671,15678,15680,15681,15685,15685,15685,15687,15691,15693,15697,15699,15702,15702,15704,15705,15706,15706,15708,15709,15710,15712,15713,15720,15722,15724,15727,15730,15733,15737,15738,15739,15750,15752,15755,15759,15761,15762,15763,15766,15767,15767,15768,15768,15770,15770,15772,15772,15775,15776,15777,15780,15785,15786,15787,15791,15791,15794,15797,15797,15799,15800,15803,15805,15810,15811,15812,15813,15814,15814,15818,15818,15819,15820,15821,15821,15821,15822,15827,15828,15828,15830,15833,15834,15835,15835,15841,15842,15845,15846,15846,15847,15850,15850,15852,15860,15863,15865,15866,15868,15868,15871,15872,15873,15875,15875,15879,15884,15886,15887,15887,15888,15889,15890,15893,15895,15896,15897,15899,15904,15904,15905,15908,15910,15912,15913,15914,15915,15917,15918,15918,15920,15923,15924,15928,15929,15929,15931,15935,15936,15937,15938,15942,15943,15943,15944,15946,15946,15950,15953,15955,15958,15959,15960,15963,15965,15975,15975,15975,15977,15979,15980,15982,15982,15983,15988,15989,15992,15993,15999,16001,16006,16008,16009,16011,16012,16017,16022,16024,16024,16025,16027,16027,16029,16029,16031,16033,16033,16036,16039,16043,16044,16047,16049,16053,16055,16056,16059,16064,16068,16069,16069,16070,16074,16074,16075,16075,16076,16078,16079,16080,16082,16082,16088,16089,16089,16091,16091,16092,16103,16104,16104,16107,16107,16108,16110,16110,16113,16113,16114,16116,16120,16120,16121,16121,16128,16131,16133,16136,16137,16138,16140,16142,16146,16149,16150,16151,16154,16155,16158,16162,16163,16164,16167,16168,16169,16173,16175,16176,16178,16179,16180,16181,16182,16190,16190,16193,16196,16198,16200,16201,16203,16204,16206,16207,16207,16208,16209,16212,16217,16219,16221,16221,16221,16227,16228,16235,16236,16238,16239,16239,16240,16240,16243,16244,16246,16246,16247,16247,16247,16249,16250,16254,16255,16257,16258,16260,16263,16266,16267,16267,16267,16270,16276,16277,16279,16281,16283,16283,16286,16287,16290,16292,16297,16297,16300,16302,16303,16305,16305,16309,16313,16314,16314,16317,16318,16320,16322,16323,16323,16326,16328,16330,16331,16333,16334,16337,16340,16340,16342,16347,16347,16348,16349,16349,16349,16350,16352,16353,16355,16356,16357,16358,16361,16361,16365,16367,16368,16375,16380,16381,16381,16382,16383,16384,16386,16386,16387,16394,16394,16396,16397,16401,16403,16404,16404,16404,16406,16409,16413,16420,16420,16420,16422,16423,16424,16425,16426,16427,16429,16429,16430,16430,16434,16435,16437,16439,16439,16439,16443,16444,16445,16449,16451,16452,16454,16454,16456,16458,16459,16460,16462,16465,16467,16468,16469,16471,16472,16472,16472,16477,16477,16478,16479,16479,16480,16482,16486,16486,16486,16488,16488,16488,16495,16495,16495,16499,16501,16502,16503,16504,16506,16511,16511,16511,16513,16515,16515,16517,16520,16523,16524,16524,16524,16525,16530,16531,16537,16539,16539,16540,16544,16545,16545,16550,16555,16555,16557,16557,16561,16564,16565,16566,16567,16574,16576,16581,16583,16584,16585,16591,16594,16594,16598,16598,16601,16601,16603,16604,16606,16608,16611,16612,16612,16613,16618,16619,16622,16624,16632,16636,16640,16642,16642,16644,16644,16646,16647,16648,16650,16654,16656,16657,16657,16660,16662,16663,16664,16664,16665,16665,16665,16667,16667,16671,16672,16672,16672,16674,16678,16679,16681,16685,16686,16690,16691,16692,16695,16696,16702,16705,16710,16712,16715,16717,16718,16720,16720,16721,16723,16724,16729,16730,16738,16751,16758,16759,16760,16760,16761,16762,16763,16764,16767,16767,16772,16775,16775,16776,16783,16784,16784,16785,16787,16790,16790,16792,16795,16810,16811,16811,16813,16815,16816,16816,16818,16818,16820,16821,16821,16822,16823,16826,16827,16830,16832,16832,16835,16837,16838,16840,16841,16844,16846,16846,16850,16862,16865,16868,16872,16876,16876,16882,16883,16884,16888,16891,16898,16901,16904,16905,16909,16909,16910,16911,16912,16913,16914,16914,16916,16919,16920,16923,16923,16924,16925,16929,16931,16931,16931,16942,16944,16945,16947,16948,16951,16955,16958,16962,16963,16963,16965,16966,16968,16968,16970,16971,16972,16972,16974,16974,16976,16977,16981,16981,16982,16982,16984,16988,16988,16990,16991,16992,16992,16993,16993,16994,16996,16996,16997,16999,16999,17001,17004,17015,17018,17020,17023,17023,17025,17028,17028,17034,17038,17038,17039,17039,17040,17041,17042,17047,17053,17053,17055,17058,17064,17065,17065,17065,17066,17067,17070,17071,17071,17072,17074,17076,17082,17084,17085,17097,17098,17102,17104,17105,17106,17106,17108,17109,17109,17110,17112,17113,17113,17117,17117,17118,17119,17122,17122,17123,17129,17130,17131,17138,17140,17146,17146,17146,17148,17148,17150,17150,17151,17153,17153,17160,17161,17166,17166,17168,17169,17175,17175,17175,17178,17178,17178,17182,17189,17191,17192,17194,17198,17199,17202,17205,17207,17207,17216,17217,17218,17224,17228,17229,17230,17232,17232,17233,17237,17240,17241,17242,17244,17245,17252,17256,17257,17260,17261,17262,17264,17265,17266,17267,17269,17270,17271,17272,17273,17277,17289,17289,17289,17290,17297,17298,17299,17300,17300,17300,17304,17304,17304,17305,17306,17307,17307,17308,17313,17315,17317,17317,17318,17319,17327,17330,17330,17332,17333,17334,17338,17340,17344,17344,17345,17346,17350,17352,17353,17362,17363,17363,17364,17365,17366,17368,17371,17378,17379,17380,17383,17392,17392,17395,17395,17397,17398,17402,17404,17407,17407,17407,17409,17409,17410,17412,17412,17423,17423,17425,17425,17429,17431,17436,17437,17438,17440,17440,17445,17450,17453,17457,17457,17458,17472,17472,17474,17475,17475,17477,17479,17480,17482,17482,17484,17486,17486,17487,17488,17489,17489,17489,17491,17491,17491,17493,17493,17495,17497,17497,17499,17500,17502,17503,17505,17505,17507,17509,17512,17514,17519,17520,17520,17521,17523,17524,17525,17527,17528,17529,17530,17531,17533,17533,17534,17534,17535,17535,17535,17537,17538,17538,17541,17542,17544,17549,17555,17555,17560,17560,17561,17561,17563,17564,17566,17567,17568,17568,17569,17569,17571,17571,17575,17586,17590,17591,17596,17596,17601,17603,17604,17606,17606,17612,17616,17617,17620,17620,17623,17626,17626,17627,17628,17630,17630,17633,17635,17639,17640,17641,17642,17648,17649,17655,17655,17656,17657,17658,17658,17666,17669,17670,17670,17672,17672,17678,17679,17681,17684,17691,17695,17696,17697,17697,17701,17703,17703,17703,17706,17706,17707,17710,17712,17714,17714,17715,17717,17722,17724,17725,17725,17727,17727,17728,17730,17735,17736,17737,17738,17740,17740,17742,17743,17745,17752,17753,17759,17762,17762,17764,17767,17772,17773,17778,17778,17781,17781,17782,17784,17784,17785,17791,17793,17793,17793,17796,17798,17804,17808,17809,17812,17817,17819,17820,17821,17821,17825,17825,17827,17831,17835,17836,17836,17840,17840,17841,17843,17845,17848,17850,17855,17856,17861,17863,17865,17867,17867,17868,17868,17874,17876,17879,17882,17884,17892,17893,17893,17894,17895,17896,17897,17897,17899,17899,17900,17903,17903,17905,17905,17910,17912,17915,17916,17919,17920,17921,17926,17932,17932,17933,17933,17935,17935,17936,17938,17939,17941,17945,17948,17951,17951,17952,17959,17959,17959,17961,17962,17963,17963,17965,17966,17968,17970,17972,17972,17976,17976,17977,17980,17982,17988,17988,17991,17993,17996,17997,18003,18003,18004,18011,18012,18013,18013,18014,18015,18015,18016,18018,18021,18024,18026,18032,18034,18034,18035,18036,18036,18037,18038,18040,18042,18046,18047,18047,18047,18050,18051,18052,18057,18058,18059,18060,18063,18063,18066,18070,18072,18073,18074,18078,18079,18080,18080,18081,18083,18085,18086,18088,18090,18091,18092,18093,18098,18100,18102,18103,18106,18112,18117,18123,18125,18131,18134,18135,18136,18138,18138,18139,18139,18140,18143,18144,18144,18147,18149,18152,18156,18158,18163,18166,18168,18169,18170,18171,18171,18172,18175,18175,18176,18176,18179,18181,18184,18184,18190,18190,18192,18193,18196,18206,18206,18206,18211,18213,18216,18217,18220,18224,18225,18225,18228,18229,18230,18231,18234,18235,18236,18238,18238,18238,18241,18248,18249,18250,18253,18255,18255,18256,18258,18260,18266,18267,18267,18275,18278,18285,18287,18288,18288,18291,18292,18292,18293,18293,18298,18299,18300,18303,18313,18314,18315,18318,18319,18320,18320,18323,18326,18326,18336,18336,18338,18340,18340,18341,18342,18343,18346,18348,18348,18350,18350,18351,18353,18355,18356,18356,18358,18359,18361,18361,18366,18369,18370,18372,18372,18373,18376,18377,18380,18381,18382,18384,18384,18392,18394,18397,18398,18400,18403,18404,18404,18407,18409,18412,18413,18414,18415,18415,18420,18422,18432,18433,18437,18440,18440,18441,18442,18446,18454,18457,18465,18467,18471,18475,18477,18483,18486,18487,18489,18496,18497,18502,18502,18503,18507,18508,18509,18510,18512,18513,18516,18516,18516,18517,18521,18526,18527,18527,18529,18530,18532,18540,18545,18548,18549,18550,18551,18552,18555,18558,18558,18563,18564,18566,18566,18566,18568,18568,18570,18575,18575,18581,18582,18583,18585,18585,18591,18595,18597,18599,18600,18603,18608,18609,18616,18616,18617,18619,18619,18620,18620,18621,18621,18621,18624,18627,18628,18630,18631,18631,18634,18635,18636,18637,18637,18637,18638,18638,18639,18639,18639,18645,18646,18647,18650,18651,18654,18654,18660,18660,18663,18668,18669,18673,18673,18678,18681,18682,18685,18688,18690,18691,18695,18698,18699,18700,18703,18704,18709,18711,18718,18724,18726,18726,18728,18736,18737,18738,18739,18741,18742,18744,18745,18745,18747,18747,18757,18757,18759,18763,18764,18764,18769,18769,18770,18773,18776,18780,18781,18787,18787,18790,18799,18800,18802,18805,18807,18807,18809,18809,18809,18810,18811,18811,18812,18813,18815,18817,18822,18828,18833,18836,18841,18842,18845,18849,18850,18850,18851,18851,18854,18856,18857,18864,18866,18867,18867,18868,18869,18869,18874,18874,18875,18876,18876,18877,18877,18877,18880,18881,18883,18886,18887,18888,18889,18893,18895,18896,18898,18900,18901,18904,18905,18905,18910,18910,18912,18915,18917,18920,18922,18922,18922,18925,18929,18930,18931,18932,18933,18935,18935,18936,18938,18938,18939,18944,18945,18945,18946,18951,18955,18957,18961,18964,18965,18965,18967,18968,18969,18975,18978,18979,18980,18982,18983,18983,18983,18987,18989,18989,18991,18992,18992,18998,18999,18999,19000,19000,19000,19003,19003,19007,19016,19018,19019,19022,19032,19032,19033,19034,19035,19036,19037,19040,19043,19044,19050,19051,19052,19052,19053,19054,19054,19055,19055,19059,19060,19060,19061,19062,19067,19068,19069,19072,19074,19082,19082,19083,19085,19086,19087,19091,19091,19096,19097,19098,19098,19103,19105,19109,19110,19111,19113,19113,19115,19115,19116,19117,19118,19122,19123,19124,19125,19127,19127,19128,19132,19133,19135,19135,19135,19140,19141,19144,19146,19147,19151,19152,19153,19158,19161,19162,19162,19165,19166,19167,19167,19172,19173,19175,19178,19183,19184,19192,19194,19196,19197,19199,19204,19204,19205,19206,19206,19206,19208,19211,19213,19214,19217,19219,19226,19227,19228,19229,19229,19232,19234,19234,19236,19237,19238,19238,19239,19240,19245,19248,19248,19249,19252,19254,19266,19266,19266,19271,19274,19275,19275,19280,19284,19286,19292,19292,19296,19300,19301,19303,19304,19306,19309,19310,19314,19315,19315,19315,19316,19316,19319,19320,19321,19324,19325,19325,19327,19333,19334,19336,19338,19339,19341,19344,19345,19346,19352,19355,19356,19357,19357,19358,19359,19362,19366,19367,19369,19370,19370,19371,19372,19378,19383,19387,19390,19390,19394,19398,19399,19400,19400,19401,19402,19406,19406,19410,19411,19412,19413,19420,19421,19423,19431,19432,19433,19436,19437,19438,19441,19442,19443,19443,19449,19451,19451,19456,19458,19459,19463,19465,19465,19466,19466,19469,19473,19475,19476,19476,19479,19482,19487,19490,19491,19491,19493,19493,19495,19496,19497,19498,19500,19501,19502,19504,19505,19505,19505,19511,19512,19514,19514,19515,19517,19519,19524,19541,19541,19542,19543,19546,19551,19551,19552,19555,19560,19561,19562,19564,19564,19565,19567,19569,19572,19575,19576,19587,19588,19588,19588,19591,19593,19594,19594,19597,19598,19599,19603,19604,19611,19612,19614,19616,19618,19624,19626,19628,19628,19628,19631,19631,19632,19634,19636,19640,19642,19643,19644,19646,19648,19649,19650,19652,19653,19655,19661,19663,19664,19664,19665,19667,19671,19672,19673,19676,19679,19680,19681,19684,19685,19687,19690,19690,19693,19693,19694,19694,19694,19697,19700,19701,19707,19719,19719,19720,19725,19726,19726,19727,19731,19734,19735,19735,19740,19743,19745,19746,19748,19749,19753,19753,19756,19757,19757,19758,19758,19759,19759,19761,19770,19773,19774,19776,19776,19777,19778,19778,19780,19785,19790,19792,19799,19800,19801,19802,19804,19804,19811,19812,19812,19813,19813,19813,19814,19815,19818,19818,19820,19827,19827,19827,19827,19834,19835,19837,19837,19840,19841,19841,19844,19844,19845,19847,19852,19858,19858,19859,19860,19871,19871,19874,19879,19881,19883,19885,19889,19893,19894,19895,19895,19897,19897,19898,19900,19901,19903,19913,19917,19918,19918,19920,19921,19922,19926,19927,19928,19929,19931,19931,19934,19936,19937,19943,19948,19949,19951,19953,19953,19958,19960,19963,19965,19969,19971,19974,19977,19982,19982,19985,19986,19990,19994,19996,19997,20000};
int difference = bubblesort(a,n);
double time = double(difference) / CLOCKS_PER_SEC;
cout<<"Time consumed = "<<time<<" sec"<<endl;
for(int i = 0; i < n; i++)
{
cout<<a[i]<<",";
}
cout<<endl;
}
int bubblesort(int arr[], int size)
{
int checker = 1;
clock_t start = clock();
for(int i = 1;i < size;i++)
{
if(checker == 1)
{
checker = 0;
for(int j = 0; j < size - i;j++)
{
if(arr[j]>arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
checker = 1;
}
}
}
else
{
break;
}
}
clock_t end = clock();
int diff = end - start;
return diff;
}