Quick-Sort.cpp

#include<iostream>
#include<conio.h>
#include<ctime>
using namespace std;


void quickSort(int *array, int low, int high)
{
    int i = low;
    int j = high;
    int pivot = array[(i + j) / 2];
    int temp;

    while (i <= j)
    {
        while (array[i] < pivot)
            i++;
        while (array[j] > pivot)
            j--;
        if (i <= j)
        {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
    }
    if (j > low)
        quickSort(array, low, j);
    if (i < high)
        quickSort(array, i, high);
}
int main()
{
int n = 10000;
	int a[n] = {0,2,3,3,4,5,5,5,6,6,7,9,11,12,14,14,16,16,17,18,20,20,23,23,23,24,25,26,27,29,29,30,31,31,32,32,33,36,37,37,38,40,43,43,45,45,47,49,49,51,55,56,57,57,58,58,60,61,62,63,64,65,66,68,69,69,70,70,70,73,74,75,76,76,77,78,79,79,80,81,81,82,83,84,84,86,87,87,90,92,94,96,97,99,101,106,106,108,109,110,111,114,114,115,116,116,117,117,118,120,123,126,126,128,128,128,129,129,130,130,131,133,133,133,133,133,134,137,138,138,140,141,142,142,143,143,144,147,150,154,155,156,157,157,158,159,162,163,165,166,167,167,167,167,168,168,168,168,168,169,169,170,171,171,172,174,174,176,176,177,177,178,179,180,181,182,183,186,186,187,187,189,189,191,191,191,192,193,193,193,194,194,194,197,198,198,199,199,200,201,203,203,204,204,205,206,208,208,209,210,210,211,212,213,213,214,215,215,216,218,218,219,219,220,222,223,223,226,227,228,230,232,232,232,234,236,237,238,238,239,240,241,241,243,244,244,245,245,246,247,249,251,251,253,253,254,254,256,258,261,261,262,262,263,264,267,267,267,268,268,268,270,271,274,274,275,275,275,276,276,277,278,280,281,282,282,283,284,285,286,288,288,290,291,291,292,293,295,298,298,299,299,303,304,305,306,307,307,307,308,310,312,312,313,316,317,318,320,321,322,322,323,323,323,324,324,325,327,328,333,334,334,335,337,338,341,343,345,345,347,348,349,350,351,354,354,355,356,356,357,360,360,362,364,364,366,366,366,367,368,369,371,371,372,373,374,378,378,380,380,382,382,383,383,384,384,385,387,387,388,390,391,391,392,392,393,394,395,395,395,396,396,397,398,399,401,401,403,405,405,405,407,408,408,408,409,409,410,410,410,411,411,412,414,414,414,414,416,418,418,418,418,418,418,419,419,420,422,422,425,427,427,428,429,432,434,434,436,439,439,439,439,440,440,441,441,442,442,442,445,445,445,446,446,447,449,450,452,452,453,454,454,454,455,455,455,456,456,456,456,457,460,465,465,466,467,468,468,470,470,471,472,473,474,476,477,477,477,478,478,481,482,484,485,489,490,490,492,493,495,495,495,495,496,496,497,499,501,501,501,502,502,503,503,504,506,506,507,508,509,509,511,512,513,513,516,516,518,520,520,522,524,526,527,528,529,530,530,530,531,532,533,534,534,535,535,535,536,536,539,541,541,542,544,544,548,548,549,549,550,552,552,553,554,555,555,556,556,557,559,560,560,560,560,561,562,566,566,566,568,568,568,569,570,571,572,574,575,575,577,577,578,580,580,583,587,587,588,592,593,594,595,597,598,598,598,599,601,601,602,602,605,605,605,606,608,611,611,611,611,612,612,614,615,615,615,620,620,620,621,621,622,623,626,626,626,626,627,627,630,630,632,637,637,638,639,641,642,642,643,645,646,646,646,647,648,649,650,650,650,651,652,652,656,656,659,659,659,661,662,663,664,665,668,669,670,672,673,674,676,676,678,680,681,681,684,684,685,685,686,686,687,688,689,692,692,694,695,695,695,697,698,699,699,699,700,701,702,703,704,704,704,704,705,705,706,707,707,709,711,711,711,713,713,714,715,715,716,716,717,717,718,721,722,722,722,725,727,730,730,731,737,737,739,740,740,741,741,741,741,742,743,743,745,747,748,748,749,749,750,751,751,752,752,752,752,753,753,754,755,757,757,760,760,760,763,763,763,765,767,767,767,767,768,770,771,771,772,773,776,776,780,783,788,790,791,792,792,794,795,795,797,799,799,799,799,800,800,801,802,802,805,805,805,807,807,808,809,809,811,812,813,813,814,816,818,818,818,821,823,824,824,825,827,827,828,829,833,835,835,837,837,840,844,845,847,847,847,850,851,852,853,853,853,853,855,855,856,856,857,858,859,860,861,862,863,863,863,865,865,866,866,867,867,867,868,868,869,872,874,875,877,878,880,881,881,882,883,884,886,887,888,888,890,891,892,892,892,892,893,893,895,895,895,896,897,898,898,899,899,899,901,903,903,905,905,906,907,908,910,910,910,911,912,913,914,917,919,921,922,922,924,926,927,928,929,930,930,931,931,931,931,932,932,932,933,933,934,937,938,938,938,939,941,942,943,944,944,945,946,947,949,949,950,950,953,956,957,959,960,960,961,962,962,962,964,965,967,968,969,969,969,969,969,973,973,973,974,975,982,983,984,985,986,986,989,990,992,992,992,993,994,994,995,996,996,997,998,998,999,1000,1000,1000,1001,1003,1005,1007,1008,1008,1010,1014,1015,1017,1017,1020,1020,1026,1028,1028,1031,1032,1033,1034,1034,1036,1037,1038,1038,1039,1042,1042,1043,1045,1047,1047,1049,1049,1051,1053,1054,1056,1056,1057,1057,1059,1060,1060,1060,1060,1061,1062,1063,1064,1067,1067,1071,1071,1071,1073,1073,1074,1076,1078,1078,1081,1081,1081,1082,1084,1086,1088,1089,1090,1090,1091,1094,1097,1097,1098,1098,1098,1099,1099,1100,1100,1100,1100,1101,1102,1103,1105,1105,1106,1110,1110,1114,1115,1116,1120,1123,1127,1127,1129,1132,1135,1136,1136,1136,1137,1138,1139,1141,1141,1142,1143,1143,1143,1145,1145,1146,1146,1146,1146,1147,1147,1148,1150,1150,1152,1152,1152,1154,1154,1155,1155,1156,1156,1157,1157,1158,1158,1161,1162,1162,1163,1164,1165,1166,1166,1166,1168,1169,1170,1173,1173,1174,1175,1176,1176,1177,1177,1179,1181,1182,1183,1184,1184,1189,1190,1191,1191,1194,1195,1197,1198,1198,1200,1200,1201,1202,1206,1206,1207,1209,1209,1209,1211,1211,1213,1217,1218,1219,1219,1219,1220,1220,1220,1221,1222,1223,1224,1224,1226,1227,1228,1228,1228,1229,1231,1231,1232,1232,1232,1235,1236,1236,1237,1238,1241,1241,1243,1243,1243,1243,1244,1245,1245,1245,1245,1246,1247,1249,1249,1252,1253,1253,1254,1255,1256,1257,1260,1261,1262,1262,1262,1263,1264,1264,1264,1268,1268,1269,1269,1270,1270,1270,1273,1273,1273,1274,1275,1276,1277,1277,1278,1278,1279,1279,1279,1280,1283,1284,1285,1286,1288,1288,1289,1289,1294,1294,1294,1298,1298,1300,1300,1300,1300,1301,1304,1307,1310,1310,1315,1315,1319,1319,1319,1319,1320,1322,1323,1323,1325,1326,1327,1327,1330,1331,1332,1332,1333,1334,1334,1335,1335,1335,1337,1338,1341,1342,1343,1345,1347,1347,1351,1352,1358,1359,1360,1361,1364,1364,1365,1366,1366,1367,1367,1369,1369,1370,1370,1371,1372,1372,1378,1380,1381,1382,1383,1384,1385,1388,1393,1394,1394,1394,1397,1399,1399,1400,1402,1403,1405,1405,1406,1409,1410,1410,1411,1411,1413,1414,1414,1415,1415,1415,1416,1416,1417,1418,1418,1418,1419,1421,1422,1423,1423,1428,1428,1430,1430,1430,1433,1433,1434,1434,1435,1435,1435,1435,1435,1437,1438,1439,1439,1439,1439,1440,1440,1442,1442,1443,1446,1446,1447,1447,1449,1453,1454,1454,1457,1459,1461,1462,1463,1463,1464,1465,1465,1465,1467,1469,1471,1471,1471,1472,1472,1473,1474,1474,1476,1476,1477,1478,1479,1479,1480,1481,1481,1485,1485,1485,1486,1487,1488,1488,1489,1490,1492,1492,1493,1494,1497,1497,1498,1498,1498,1500,1500,1501,1501,1501,1502,1504,1505,1506,1506,1508,1509,1509,1510,1511,1513,1514,1514,1514,1515,1515,1516,1516,1517,1517,1519,1521,1521,1522,1524,1526,1527,1527,1528,1529,1531,1533,1533,1535,1536,1538,1539,1541,1541,1542,1542,1542,1542,1543,1543,1544,1545,1547,1547,1548,1548,1548,1553,1556,1557,1557,1558,1561,1563,1563,1563,1564,1565,1566,1567,1568,1568,1568,1570,1572,1573,1574,1577,1577,1579,1579,1580,1581,1582,1583,1583,1583,1585,1588,1589,1589,1598,1598,1599,1602,1602,1604,1604,1605,1605,1608,1609,1610,1610,1611,1611,1612,1613,1614,1615,1615,1615,1618,1618,1619,1619,1622,1622,1623,1623,1623,1624,1624,1625,1625,1626,1626,1626,1626,1627,1628,1628,1630,1631,1632,1632,1632,1633,1634,1635,1635,1638,1639,1640,1641,1641,1642,1642,1642,1643,1644,1645,1649,1649,1650,1655,1655,1657,1659,1659,1660,1661,1661,1662,1662,1663,1664,1665,1667,1668,1670,1671,1671,1672,1674,1674,1675,1679,1679,1679,1679,1681,1682,1683,1684,1685,1687,1687,1687,1688,1689,1691,1691,1692,1692,1692,1693,1693,1693,1695,1696,1698,1698,1700,1701,1702,1702,1703,1704,1705,1705,1706,1710,1711,1711,1712,1712,1713,1713,1714,1719,1719,1720,1721,1722,1723,1723,1723,1724,1724,1724,1725,1725,1726,1728,1729,1730,1730,1731,1732,1733,1733,1735,1735,1735,1736,1737,1737,1738,1740,1740,1740,1740,1741,1742,1743,1744,1744,1745,1745,1746,1746,1747,1747,1747,1748,1749,1750,1752,1756,1757,1757,1759,1759,1762,1762,1762,1764,1764,1764,1765,1766,1766,1767,1767,1767,1768,1769,1771,1771,1772,1772,1773,1773,1773,1774,1774,1774,1776,1776,1779,1779,1779,1781,1782,1783,1784,1784,1784,1784,1785,1785,1786,1786,1787,1788,1788,1791,1791,1795,1796,1796,1798,1798,1799,1801,1802,1802,1803,1804,1806,1807,1808,1809,1813,1814,1814,1816,1816,1816,1817,1821,1822,1830,1830,1831,1831,1832,1833,1835,1835,1835,1835,1836,1839,1841,1843,1844,1845,1846,1848,1850,1851,1851,1853,1854,1856,1858,1859,1860,1861,1862,1864,1864,1865,1867,1867,1867,1867,1869,1871,1875,1876,1877,1878,1878,1878,1879,1879,1881,1882,1882,1884,1884,1884,1885,1886,1887,1888,1888,1889,1890,1890,1890,1892,1895,1895,1896,1896,1897,1897,1900,1901,1901,1902,1902,1902,1903,1903,1904,1906,1906,1907,1908,1912,1913,1915,1916,1917,1918,1918,1918,1919,1920,1920,1921,1922,1924,1924,1926,1926,1927,1927,1929,1929,1929,1929,1930,1931,1931,1931,1932,1933,1933,1933,1935,1935,1937,1937,1937,1938,1939,1939,1939,1940,1940,1941,1941,1941,1942,1942,1948,1949,1950,1951,1952,1953,1954,1955,1955,1956,1958,1959,1959,1960,1960,1962,1964,1965,1967,1968,1968,1968,1970,1970,1971,1972,1977,1978,1978,1979,1979,1979,1979,1981,1982,1983,1984,1985,1985,1985,1986,1987,1988,1989,1990,1991,1991,1991,1991,1993,1993,1995,1996,1996,1996,1996,1996,1996,1996,1998,1998,1999,1999,2000,2000,2002,2003,2004,2004,2004,2004,2005,2007,2008,2009,2009,2010,2010,2013,2013,2014,2017,2019,2020,2021,2024,2025,2026,2027,2028,2028,2028,2029,2029,2030,2032,2035,2035,2039,2042,2042,2043,2044,2046,2046,2047,2050,2052,2054,2055,2055,2056,2056,2057,2057,2058,2058,2060,2062,2062,2063,2064,2069,2069,2071,2071,2071,2072,2074,2075,2076,2076,2076,2077,2077,2078,2080,2082,2083,2085,2087,2087,2087,2088,2089,2090,2093,2093,2094,2094,2094,2094,2094,2097,2101,2102,2105,2105,2105,2106,2106,2108,2108,2109,2109,2111,2111,2112,2112,2113,2115,2115,2115,2121,2121,2122,2123,2124,2125,2125,2127,2130,2132,2134,2135,2136,2136,2137,2138,2138,2140,2142,2144,2144,2144,2145,2145,2146,2147,2147,2147,2147,2148,2149,2156,2156,2157,2157,2158,2158,2159,2162,2162,2165,2166,2167,2168,2168,2169,2170,2171,2172,2174,2174,2176,2178,2178,2179,2179,2179,2180,2181,2185,2187,2187,2189,2189,2190,2190,2190,2191,2191,2191,2192,2193,2194,2195,2197,2197,2197,2197,2199,2200,2200,2201,2202,2203,2205,2206,2206,2207,2210,2210,2211,2212,2213,2213,2214,2214,2215,2216,2218,2218,2218,2219,2219,2220,2221,2221,2221,2221,2222,2222,2223,2223,2223,2225,2226,2227,2228,2228,2230,2231,2231,2232,2233,2234,2235,2235,2236,2236,2238,2238,2239,2240,2242,2243,2243,2251,2252,2253,2254,2256,2257,2261,2261,2262,2264,2266,2266,2266,2266,2269,2272,2273,2274,2274,2276,2277,2278,2278,2280,2281,2283,2283,2284,2284,2287,2287,2288,2288,2288,2292,2294,2295,2296,2296,2297,2299,2300,2301,2301,2302,2303,2303,2304,2308,2309,2309,2310,2311,2312,2313,2315,2315,2324,2324,2326,2328,2329,2330,2331,2332,2332,2333,2334,2334,2334,2335,2336,2339,2340,2341,2341,2342,2342,2342,2343,2344,2344,2344,2346,2346,2346,2347,2347,2348,2350,2351,2352,2352,2353,2355,2355,2355,2356,2357,2358,2360,2362,2364,2364,2364,2366,2368,2368,2368,2368,2369,2370,2370,2370,2370,2371,2374,2377,2378,2380,2380,2381,2381,2381,2381,2382,2382,2387,2387,2387,2388,2388,2388,2388,2389,2392,2395,2395,2396,2396,2397,2399,2400,2400,2401,2402,2403,2403,2405,2405,2405,2407,2408,2409,2412,2412,2413,2413,2413,2414,2414,2418,2419,2419,2421,2423,2423,2424,2424,2424,2425,2426,2426,2428,2429,2429,2432,2432,2432,2433,2434,2434,2438,2438,2440,2440,2440,2441,2442,2443,2445,2445,2445,2445,2445,2446,2446,2446,2446,2448,2449,2452,2455,2456,2456,2457,2458,2458,2459,2459,2460,2461,2463,2463,2464,2465,2465,2465,2468,2469,2470,2470,2471,2472,2472,2474,2474,2474,2474,2476,2477,2477,2477,2478,2480,2481,2481,2482,2482,2482,2483,2483,2484,2486,2486,2489,2489,2489,2491,2491,2492,2492,2492,2492,2494,2496,2497,2497,2497,2498,2498,2498,2499,2500,2500,2504,2504,2504,2504,2504,2505,2506,2507,2507,2508,2509,2510,2510,2510,2510,2510,2511,2512,2514,2515,2515,2515,2516,2518,2520,2520,2520,2521,2523,2524,2525,2525,2525,2526,2526,2526,2528,2528,2530,2531,2531,2534,2534,2534,2535,2537,2538,2540,2540,2540,2540,2540,2542,2542,2544,2544,2546,2550,2550,2551,2555,2556,2558,2558,2559,2559,2559,2559,2560,2560,2560,2561,2561,2564,2564,2565,2565,2566,2567,2568,2568,2568,2572,2573,2573,2573,2573,2573,2575,2576,2577,2579,2579,2580,2580,2581,2584,2587,2592,2593,2593,2594,2595,2596,2596,2597,2598,2600,2601,2601,2603,2603,2604,2606,2606,2606,2607,2608,2609,2609,2610,2610,2611,2613,2613,2614,2615,2617,2617,2618,2623,2626,2626,2628,2631,2632,2632,2633,2634,2636,2637,2637,2640,2642,2643,2643,2645,2647,2648,2648,2648,2649,2651,2651,2652,2655,2657,2660,2660,2661,2662,2663,2665,2669,2669,2670,2671,2672,2672,2672,2673,2674,2675,2675,2679,2680,2681,2682,2683,2684,2684,2684,2684,2685,2686,2686,2689,2690,2690,2690,2693,2693,2695,2695,2696,2697,2697,2697,2699,2700,2701,2704,2705,2707,2708,2710,2713,2715,2715,2718,2718,2719,2719,2720,2721,2721,2722,2723,2724,2724,2725,2725,2726,2727,2728,2729,2729,2731,2736,2736,2737,2737,2738,2738,2738,2738,2743,2744,2745,2746,2746,2746,2746,2747,2747,2750,2750,2751,2751,2755,2756,2758,2759,2759,2759,2761,2762,2764,2765,2766,2766,2768,2769,2769,2770,2771,2772,2775,2775,2777,2777,2777,2779,2780,2782,2782,2783,2783,2784,2786,2787,2787,2788,2788,2788,2791,2791,2792,2792,2793,2794,2796,2797,2798,2800,2801,2802,2804,2804,2805,2807,2808,2809,2809,2809,2809,2810,2810,2813,2814,2815,2815,2816,2816,2817,2818,2819,2821,2821,2822,2822,2823,2823,2823,2824,2824,2825,2825,2826,2827,2828,2831,2832,2832,2833,2834,2834,2835,2835,2836,2838,2838,2838,2839,2840,2840,2843,2843,2845,2848,2848,2849,2854,2855,2855,2855,2855,2857,2857,2859,2859,2862,2863,2863,2864,2865,2867,2868,2869,2869,2869,2870,2870,2871,2871,2872,2872,2874,2874,2874,2875,2875,2875,2877,2877,2877,2879,2880,2881,2883,2885,2886,2887,2890,2891,2892,2895,2897,2898,2898,2898,2899,2900,2901,2901,2902,2905,2906,2908,2910,2911,2912,2915,2917,2917,2917,2918,2919,2921,2922,2925,2925,2926,2926,2927,2927,2927,2927,2928,2929,2930,2932,2932,2932,2932,2935,2935,2935,2937,2937,2941,2943,2943,2943,2943,2945,2949,2949,2952,2952,2953,2954,2957,2958,2958,2958,2958,2959,2959,2960,2961,2961,2962,2963,2963,2969,2970,2970,2971,2972,2972,2973,2974,2975,2975,2976,2976,2976,2977,2977,2978,2978,2979,2979,2979,2979,2979,2980,2980,2980,2981,2981,2983,2983,2983,2985,2985,2986,2987,2991,2992,2993,2995,2995,2995,2996,2997,2998,2999,3000,3000,3000,3001,3001,3003,3003,3004,3004,3007,3008,3009,3010,3012,3015,3015,3016,3017,3018,3018,3020,3020,3020,3021,3024,3024,3024,3025,3026,3026,3026,3026,3028,3029,3031,3032,3033,3033,3034,3034,3035,3036,3037,3039,3039,3039,3040,3042,3042,3046,3048,3048,3049,3050,3050,3050,3051,3051,3052,3054,3055,3056,3056,3059,3060,3063,3065,3065,3067,3067,3068,3068,3071,3072,3072,3073,3074,3074,3077,3077,3078,3078,3078,3079,3079,3079,3080,3080,3082,3082,3083,3083,3086,3087,3087,3088,3089,3091,3091,3095,3095,3096,3097,3098,3099,3100,3101,3104,3104,3106,3106,3109,3109,3109,3110,3110,3113,3113,3114,3114,3115,3115,3117,3118,3119,3125,3129,3131,3133,3133,3136,3136,3137,3138,3138,3139,3140,3140,3140,3142,3143,3145,3145,3152,3152,3154,3154,3155,3155,3156,3157,3159,3160,3160,3161,3163,3165,3165,3165,3167,3167,3167,3167,3167,3167,3169,3170,3171,3171,3171,3172,3174,3174,3176,3177,3177,3177,3179,3182,3184,3185,3185,3187,3189,3189,3190,3190,3191,3194,3194,3195,3195,3195,3196,3197,3197,3198,3199,3200,3201,3201,3202,3203,3203,3203,3204,3205,3205,3207,3208,3208,3209,3209,3210,3210,3210,3210,3211,3213,3214,3215,3217,3217,3217,3219,3221,3222,3222,3223,3224,3225,3226,3227,3227,3229,3229,3231,3232,3232,3233,3237,3238,3238,3239,3239,3240,3241,3241,3241,3243,3243,3244,3245,3246,3247,3247,3248,3248,3248,3250,3251,3251,3252,3253,3254,3255,3257,3258,3258,3258,3259,3259,3260,3264,3265,3267,3268,3269,3270,3271,3272,3272,3273,3275,3275,3278,3279,3280,3281,3281,3282,3285,3287,3287,3287,3287,3289,3289,3290,3291,3293,3294,3295,3296,3297,3297,3297,3299,3299,3300,3302,3303,3307,3309,3309,3310,3311,3314,3316,3316,3316,3316,3316,3317,3317,3317,3319,3322,3324,3324,3325,3326,3326,3327,3328,3330,3332,3332,3332,3333,3335,3337,3339,3339,3339,3340,3341,3343,3344,3344,3344,3344,3344,3344,3344,3345,3345,3348,3348,3350,3354,3354,3354,3355,3355,3355,3357,3357,3357,3358,3359,3362,3363,3366,3366,3366,3367,3368,3369,3371,3371,3373,3375,3375,3377,3378,3379,3379,3379,3380,3381,3384,3384,3384,3386,3386,3386,3387,3388,3388,3391,3392,3392,3392,3392,3392,3393,3394,3394,3395,3399,3399,3400,3401,3402,3402,3403,3403,3404,3404,3406,3408,3409,3411,3413,3414,3414,3414,3415,3416,3416,3417,3419,3420,3422,3423,3425,3425,3426,3428,3430,3431,3431,3433,3434,3435,3436,3437,3437,3437,3439,3442,3442,3442,3443,3447,3448,3448,3449,3450,3451,3452,3452,3453,3454,3455,3457,3457,3457,3458,3458,3459,3460,3462,3464,3465,3465,3466,3466,3467,3467,3469,3471,3471,3472,3473,3474,3475,3477,3478,3480,3482,3484,3484,3484,3487,3488,3489,3489,3490,3491,3491,3491,3494,3496,3497,3498,3499,3500,3503,3503,3504,3506,3507,3510,3513,3515,3515,3517,3517,3518,3520,3520,3520,3520,3524,3524,3529,3530,3531,3531,3532,3534,3535,3536,3536,3538,3540,3542,3543,3544,3546,3548,3548,3548,3550,3551,3551,3555,3555,3555,3556,3557,3557,3559,3560,3560,3561,3563,3565,3566,3567,3568,3569,3570,3570,3572,3573,3574,3574,3574,3575,3575,3576,3576,3576,3577,3577,3579,3579,3581,3581,3581,3585,3585,3585,3586,3587,3588,3588,3590,3590,3590,3591,3591,3592,3593,3594,3595,3596,3596,3597,3598,3600,3600,3601,3602,3604,3605,3606,3609,3611,3611,3613,3613,3616,3616,3617,3618,3619,3621,3626,3626,3626,3628,3628,3629,3629,3630,3630,3631,3631,3632,3632,3632,3632,3632,3633,3635,3635,3636,3636,3638,3638,3641,3642,3643,3644,3644,3644,3646,3647,3648,3649,3649,3649,3649,3649,3650,3651,3652,3653,3654,3656,3657,3657,3657,3658,3658,3658,3659,3659,3660,3661,3661,3662,3664,3665,3666,3667,3669,3670,3671,3671,3673,3673,3673,3674,3676,3676,3676,3677,3678,3678,3679,3680,3682,3683,3683,3687,3688,3689,3691,3692,3692,3693,3695,3695,3697,3698,3699,3699,3704,3704,3705,3708,3709,3709,3711,3711,3712,3713,3715,3716,3716,3717,3717,3719,3720,3720,3721,3722,3724,3724,3724,3725,3725,3726,3727,3730,3731,3731,3732,3732,3734,3736,3737,3737,3737,3737,3738,3739,3740,3741,3744,3745,3746,3746,3748,3751,3751,3755,3756,3756,3757,3757,3758,3758,3758,3759,3762,3762,3763,3763,3764,3764,3766,3768,3769,3769,3769,3770,3771,3772,3775,3776,3778,3778,3778,3779,3779,3782,3782,3783,3783,3785,3785,3786,3786,3786,3786,3787,3787,3788,3789,3790,3791,3792,3794,3794,3797,3797,3797,3800,3800,3803,3804,3806,3807,3807,3808,3809,3810,3811,3812,3814,3815,3817,3818,3820,3821,3821,3822,3824,3825,3825,3828,3828,3831,3836,3837,3837,3838,3838,3840,3840,3841,3843,3845,3847,3848,3849,3852,3854,3854,3856,3857,3859,3859,3861,3863,3863,3864,3865,3865,3865,3866,3866,3867,3867,3871,3874,3874,3874,3875,3877,3879,3880,3881,3883,3885,3885,3891,3894,3895,3896,3902,3903,3905,3907,3907,3909,3911,3911,3911,3912,3913,3913,3914,3914,3915,3915,3915,3915,3917,3918,3918,3918,3918,3919,3923,3924,3927,3928,3929,3930,3931,3931,3931,3932,3933,3935,3936,3938,3939,3944,3944,3944,3945,3945,3945,3946,3946,3948,3948,3948,3949,3950,3953,3953,3954,3955,3957,3957,3958,3959,3959,3959,3959,3959,3960,3960,3961,3962,3963,3965,3966,3966,3966,3967,3968,3969,3970,3971,3971,3971,3971,3973,3975,3975,3978,3979,3979,3981,3985,3985,3985,3985,3987,3988,3988,3988,3989,3989,3990,3990,3992,3994,3995,3996,3997,3997,3997,3999,3999,4000,4000,4001,4002,4002,4002,4003,4003,4003,4004,4006,4009,4011,4011,4012,4013,4014,4015,4016,4016,4017,4018,4018,4020,4021,4024,4024,4025,4026,4027,4027,4027,4028,4028,4029,4029,4030,4033,4034,4034,4036,4037,4037,4038,4038,4040,4040,4040,4040,4041,4044,4044,4044,4045,4046,4046,4047,4049,4050,4051,4051,4051,4054,4056,4057,4058,4059,4059,4059,4059,4060,4061,4061,4063,4063,4064,4066,4067,4069,4069,4071,4071,4071,4072,4072,4072,4072,4073,4074,4075,4076,4078,4079,4080,4081,4081,4081,4082,4084,4085,4085,4087,4088,4088,4089,4090,4091,4092,4092,4093,4094,4096,4096,4098,4099,4099,4099,4100,4100,4104,4107,4108,4108,4108,4109,4110,4110,4110,4112,4112,4112,4113,4113,4114,4115,4118,4118,4118,4121,4122,4124,4124,4125,4126,4126,4128,4131,4135,4135,4136,4138,4141,4141,4142,4142,4144,4145,4147,4149,4152,4153,4154,4154,4155,4155,4157,4158,4158,4161,4161,4162,4162,4162,4164,4165,4165,4167,4168,4168,4168,4169,4171,4171,4172,4172,4174,4175,4179,4179,4179,4180,4180,4181,4183,4183,4184,4184,4184,4186,4186,4188,4189,4190,4193,4197,4197,4198,4198,4199,4199,4201,4203,4205,4206,4207,4207,4209,4211,4211,4212,4212,4212,4216,4216,4216,4217,4217,4218,4218,4218,4219,4219,4219,4220,4221,4221,4221,4221,4222,4224,4224,4225,4226,4226,4227,4227,4228,4229,4230,4235,4237,4238,4239,4239,4239,4240,4242,4243,4244,4247,4247,4249,4251,4251,4252,4253,4254,4254,4255,4256,4257,4258,4259,4261,4263,4268,4269,4269,4271,4271,4272,4275,4277,4277,4280,4281,4282,4285,4285,4285,4287,4289,4289,4290,4290,4290,4290,4293,4294,4295,4297,4299,4300,4300,4303,4304,4305,4305,4305,4305,4306,4307,4308,4309,4309,4310,4311,4311,4312,4312,4312,4313,4314,4314,4314,4315,4315,4315,4318,4318,4319,4319,4320,4322,4323,4324,4324,4326,4327,4327,4329,4329,4329,4329,4332,4332,4332,4332,4333,4334,4334,4336,4337,4338,4339,4340,4343,4343,4345,4345,4349,4349,4349,4349,4349,4350,4352,4353,4354,4354,4354,4355,4355,4356,4359,4360,4361,4371,4372,4374,4374,4374,4376,4377,4380,4382,4384,4385,4386,4387,4391,4391,4392,4392,4392,4393,4394,4394,4394,4394,4396,4397,4398,4400,4400,4401,4401,4402,4407,4410,4410,4410,4411,4411,4411,4414,4415,4415,4417,4421,4422,4427,4427,4427,4427,4427,4429,4432,4432,4432,4433,4433,4435,4436,4438,4444,4445,4450,4452,4452,4456,4458,4458,4458,4459,4461,4462,4463,4465,4466,4469,4469,4470,4471,4472,4473,4474,4474,4475,4475,4475,4476,4477,4477,4481,4481,4483,4483,4484,4484,4484,4485,4486,4486,4486,4487,4488,4488,4489,4493,4495,4495,4497,4497,4497,4502,4507,4507,4508,4508,4508,4510,4511,4513,4518,4518,4518,4519,4519,4523,4523,4523,4524,4524,4526,4527,4527,4529,4530,4531,4532,4532,4534,4535,4535,4535,4535,4536,4536,4537,4537,4538,4540,4540,4541,4543,4544,4544,4544,4546,4546,4548,4549,4549,4549,4549,4550,4551,4552,4552,4554,4554,4555,4556,4556,4557,4558,4560,4560,4560,4561,4562,4563,4564,4566,4567,4568,4569,4569,4570,4570,4572,4572,4572,4572,4573,4573,4575,4576,4578,4579,4579,4579,4580,4581,4581,4585,4585,4585,4585,4588,4590,4592,4592,4592,4592,4593,4593,4595,4596,4598,4598,4598,4600,4604,4606,4606,4606,4607,4607,4611,4611,4611,4612,4614,4615,4615,4616,4616,4617,4617,4618,4619,4619,4620,4622,4622,4623,4624,4625,4626,4628,4628,4630,4631,4632,4632,4633,4633,4634,4635,4635,4638,4638,4638,4639,4640,4640,4640,4641,4641,4642,4642,4644,4645,4646,4646,4646,4647,4647,4647,4648,4648,4648,4648,4649,4649,4650,4650,4654,4655,4655,4656,4658,4658,4660,4660,4660,4661,4662,4662,4664,4665,4668,4669,4669,4670,4671,4672,4672,4672,4672,4674,4675,4675,4675,4675,4675,4679,4681,4681,4683,4684,4685,4688,4688,4692,4693,4693,4693,4695,4696,4696,4697,4697,4697,4698,4698,4698,4700,4700,4701,4702,4703,4709,4712,4712,4713,4714,4714,4714,4714,4715,4715,4718,4718,4721,4722,4724,4724,4724,4726,4727,4727,4728,4728,4729,4730,4730,4730,4733,4733,4737,4737,4741,4741,4742,4743,4744,4745,4745,4745,4750,4750,4751,4753,4754,4755,4757,4758,4759,4759,4759,4760,4762,4762,4762,4763,4763,4764,4765,4767,4768,4768,4769,4769,4771,4771,4772,4775,4775,4775,4776,4777,4777,4777,4779,4780,4781,4782,4783,4783,4783,4783,4785,4785,4788,4789,4789,4790,4791,4791,4792,4792,4792,4794,4796,4798,4799,4800,4800,4803,4803,4806,4807,4808,4808,4809,4809,4810,4811,4813,4814,4814,4814,4815,4815,4816,4817,4818,4821,4821,4822,4823,4823,4824,4824,4825,4825,4825,4825,4826,4827,4827,4828,4829,4830,4830,4831,4832,4832,4834,4834,4835,4835,4835,4836,4837,4838,4839,4839,4840,4840,4840,4841,4841,4841,4841,4843,4843,4843,4843,4844,4845,4846,4847,4847,4848,4848,4849,4850,4851,4852,4852,4853,4855,4855,4856,4859,4860,4860,4861,4862,4863,4864,4866,4867,4868,4869,4871,4871,4871,4872,4873,4874,4875,4875,4876,4876,4876,4877,4878,4880,4881,4882,4883,4888,4888,4891,4892,4892,4893,4894,4894,4895,4895,4896,4896,4897,4897,4899,4902,4902,4903,4903,4906,4908,4908,4910,4912,4912,4913,4913,4915,4915,4917,4918,4919,4920,4921,4921,4922,4924,4928,4929,4930,4930,4931,4931,4932,4932,4934,4934,4938,4942,4942,4943,4944,4945,4951,4955,4956,4957,4958,4958,4959,4959,4960,4960,4961,4962,4962,4963,4963,4963,4965,4965,4966,4968,4968,4968,4969,4971,4971,4973,4974,4978,4978,4978,4979,4980,4982,4983,4983,4985,4985,4986,4989,4989,4990,4990,4990,4992,4992,4994,4996,4997,4997,4998,4999,5000,5000,5001,5002,5002,5002,5002,5003,5004,5004,5005,5005,5005,5006,5006,5007,5007,5008,5010,5010,5011,5012,5012,5012,5014,5017,5017,5019,5019,5022,5022,5025,5025,5030,5030,5031,5031,5033,5035,5038,5041,5041,5041,5044,5046,5047,5049,5049,5050,5051,5054,5054,5055,5056,5056,5057,5057,5059,5061,5063,5064,5064,5064,5065,5065,5066,5068,5073,5074,5074,5075,5077,5078,5081,5082,5086,5086,5086,5086,5087,5089,5093,5096,5096,5097,5097,5097,5098,5098,5099,5100,5103,5105,5107,5108,5109,5110,5111,5111,5112,5116,5121,5121,5122,5122,5125,5125,5126,5126,5128,5128,5128,5131,5132,5133,5133,5137,5137,5142,5143,5143,5143,5144,5145,5145,5145,5146,5146,5148,5149,5150,5150,5153,5153,5154,5156,5157,5157,5158,5159,5161,5161,5162,5163,5164,5164,5164,5164,5164,5164,5165,5166,5169,5169,5169,5169,5171,5174,5176,5176,5178,5180,5182,5182,5183,5183,5186,5188,5188,5189,5189,5190,5191,5192,5194,5195,5195,5196,5196,5197,5197,5197,5198,5198,5199,5200,5201,5201,5201,5202,5203,5205,5206,5206,5207,5207,5208,5208,5208,5208,5211,5212,5212,5213,5216,5217,5217,5217,5218,5220,5220,5221,5222,5222,5222,5223,5226,5226,5227,5228,5229,5233,5234,5234,5237,5237,5237,5238,5239,5240,5241,5242,5242,5242,5242,5247,5248,5249,5250,5251,5251,5252,5252,5254,5254,5256,5260,5260,5260,5262,5263,5264,5265,5265,5266,5266,5268,5272,5272,5272,5273,5273,5276,5276,5280,5281,5281,5281,5283,5285,5285,5286,5286,5287,5288,5288,5289,5289,5290,5292,5292,5293,5296,5296,5297,5298,5299,5301,5301,5303,5303,5304,5305,5305,5307,5308,5310,5310,5312,5314,5317,5317,5318,5318,5319,5321,5323,5326,5327,5327,5327,5327,5329,5329,5330,5333,5334,5334,5335,5335,5336,5337,5342,5344,5346,5348,5348,5349,5350,5351,5352,5355,5355,5356,5357,5358,5358,5358,5358,5359,5361,5361,5362,5363,5364,5366,5367,5368,5369,5369,5370,5376,5376,5377,5379,5379,5380,5380,5382,5382,5382,5383,5383,5384,5384,5387,5388,5389,5390,5390,5390,5390,5390,5390,5392,5393,5393,5394,5395,5395,5397,5398,5398,5398,5399,5399,5399,5400,5400,5401,5401,5401,5402,5404,5404,5405,5405,5405,5405,5406,5412,5416,5417,5417,5418,5418,5418,5419,5420,5420,5420,5420,5421,5421,5424,5425,5427,5428,5428,5429,5429,5431,5433,5433,5435,5435,5437,5439,5441,5442,5445,5445,5446,5447,5448,5448,5449,5449,5451,5452,5453,5454,5454,5454,5455,5455,5456,5457,5458,5460,5460,5461,5462,5463,5464,5465,5466,5466,5466,5468,5470,5472,5473,5474,5476,5478,5478,5479,5479,5479,5479,5480,5481,5483,5484,5485,5486,5487,5487,5487,5488,5494,5494,5495,5495,5495,5496,5496,5497,5497,5498,5498,5499,5499,5500,5501,5502,5502,5505,5505,5505,5506,5507,5507,5507,5508,5509,5510,5511,5511,5511,5512,5513,5517,5517,5517,5517,5518,5518,5519,5521,5521,5522,5522,5526,5526,5526,5528,5531,5532,5534,5534,5535,5535,5535,5537,5537,5540,5543,5545,5545,5546,5546,5548,5549,5549,5552,5553,5557,5559,5559,5560,5560,5561,5561,5563,5563,5563,5564,5566,5566,5569,5569,5570,5572,5573,5574,5574,5576,5576,5576,5577,5577,5578,5578,5578,5581,5584,5584,5586,5586,5587,5590,5590,5591,5592,5592,5592,5593,5596,5596,5598,5598,5598,5601,5601,5602,5604,5604,5604,5605,5610,5611,5611,5612,5612,5613,5614,5614,5615,5615,5615,5616,5616,5616,5618,5620,5620,5621,5622,5622,5624,5626,5627,5628,5629,5629,5632,5633,5635,5635,5636,5636,5639,5639,5641,5642,5643,5644,5648,5649,5649,5651,5653,5653,5653,5654,5654,5657,5657,5658,5660,5662,5665,5667,5667,5667,5669,5669,5670,5671,5672,5673,5674,5674,5674,5675,5678,5678,5679,5679,5679,5679,5680,5681,5681,5682,5683,5683,5683,5684,5684,5684,5684,5685,5686,5686,5686,5686,5687,5689,5689,5691,5693,5694,5696,5698,5699,5702,5702,5704,5704,5704,5710,5712,5713,5714,5715,5715,5715,5715,5717,5719,5719,5720,5722,5722,5723,5723,5725,5725,5726,5730,5731,5731,5734,5735,5736,5738,5738,5738,5739,5740,5740,5740,5740,5740,5741,5742,5743,5744,5745,5745,5745,5745,5746,5747,5747,5748,5749,5751,5751,5752,5752,5754,5755,5755,5756,5756,5756,5759,5759,5760,5760,5761,5761,5762,5764,5764,5764,5764,5765,5769,5770,5771,5772,5772,5773,5776,5779,5779,5780,5781,5782,5783,5785,5785,5791,5791,5792,5793,5794,5795,5797,5802,5804,5805,5805,5807,5808,5810,5810,5811,5812,5814,5814,5816,5817,5819,5819,5820,5821,5822,5825,5825,5828,5829,5833,5833,5834,5834,5834,5835,5837,5837,5837,5837,5838,5839,5840,5843,5843,5843,5848,5849,5850,5851,5857,5858,5859,5860,5860,5861,5862,5863,5864,5864,5866,5866,5866,5867,5867,5867,5870,5872,5872,5873,5874,5875,5875,5876,5877,5877,5878,5881,5882,5882,5882,5882,5883,5883,5883,5884,5884,5884,5886,5886,5888,5893,5894,5895,5895,5896,5897,5897,5898,5899,5900,5901,5901,5905,5906,5906,5909,5909,5909,5910,5910,5910,5914,5914,5914,5914,5915,5916,5919,5920,5923,5923,5924,5924,5925,5928,5930,5930,5931,5932,5933,5934,5935,5935,5937,5940,5941,5943,5943,5945,5946,5946,5947,5949,5950,5951,5951,5952,5952,5955,5957,5959,5960,5960,5960,5961,5961,5963,5965,5965,5965,5967,5967,5970,5971,5971,5971,5971,5972,5972,5976,5978,5979,5981,5981,5982,5982,5983,5983,5987,5989,5991,5991,5992,5992,5993,5994,5994,5998,5998,5999,5999,6000,6004,6005,6006,6006,6006,6009,6011,6011,6011,6012,6013,6013,6018,6018,6018,6019,6023,6023,6024,6024,6026,6026,6027,6029,6031,6031,6032,6033,6034,6034,6034,6035,6035,6038,6038,6039,6040,6040,6041,6041,6041,6042,6045,6048,6049,6049,6050,6052,6054,6055,6055,6055,6056,6056,6058,6058,6058,6059,6060,6062,6062,6062,6064,6065,6066,6066,6067,6068,6068,6069,6070,6070,6070,6071,6072,6076,6079,6079,6080,6080,6080,6081,6081,6082,6083,6084,6085,6085,6086,6087,6087,6089,6090,6090,6091,6091,6091,6092,6095,6096,6097,6098,6098,6100,6100,6105,6106,6106,6108,6108,6109,6111,6111,6112,6113,6114,6114,6118,6118,6120,6120,6121,6121,6121,6122,6124,6124,6127,6127,6127,6128,6128,6129,6130,6130,6131,6132,6132,6133,6134,6136,6137,6139,6139,6139,6139,6140,6140,6141,6143,6143,6143,6144,6144,6145,6145,6145,6146,6146,6146,6146,6147,6149,6150,6151,6154,6154,6157,6157,6157,6158,6159,6160,6160,6160,6162,6162,6163,6164,6166,6166,6168,6168,6169,6170,6170,6171,6174,6174,6175,6177,6180,6182,6183,6184,6185,6185,6186,6187,6194,6194,6196,6196,6200,6201,6201,6201,6201,6202,6202,6205,6206,6206,6207,6207,6210,6211,6211,6212,6213,6214,6215,6217,6219,6220,6221,6222,6223,6225,6225,6227,6227,6228,6229,6229,6230,6230,6231,6231,6232,6232,6232,6233,6234,6234,6234,6235,6235,6237,6237,6237,6239,6239,6240,6241,6242,6242,6243,6243,6245,6245,6245,6246,6246,6248,6250,6251,6252,6252,6254,6255,6255,6256,6256,6256,6257,6259,6259,6260,6261,6264,6265,6265,6266,6267,6269,6270,6270,6270,6273,6275,6276,6278,6280,6281,6281,6281,6283,6284,6284,6285,6285,6286,6286,6287,6288,6291,6292,6293,6293,6294,6294,6294,6295,6296,6296,6298,6299,6300,6300,6300,6301,6301,6301,6302,6303,6305,6305,6305,6310,6311,6312,6316,6316,6317,6317,6319,6319,6321,6323,6323,6324,6325,6325,6326,6327,6327,6328,6328,6329,6332,6332,6333,6333,6335,6336,6337,6339,6340,6340,6342,6345,6346,6346,6347,6349,6352,6355,6356,6357,6357,6360,6361,6362,6362,6363,6363,6366,6366,6367,6368,6370,6370,6372,6373,6375,6376,6376,6376,6377,6378,6378,6378,6379,6379,6382,6382,6385,6386,6386,6386,6387,6388,6388,6388,6389,6390,6391,6391,6392,6392,6393,6394,6395,6396,6398,6399,6399,6400,6401,6403,6403,6404,6404,6405,6411,6411,6411,6413,6413,6413,6415,6415,6416,6418,6419,6421,6424,6426,6426,6427,6428,6428,6429,6431,6431,6431,6432,6432,6433,6434,6436,6436,6436,6438,6438,6439,6443,6443,6444,6446,6446,6446,6446,6447,6447,6447,6448,6448,6450,6453,6454,6454,6455,6457,6460,6461,6461,6463,6463,6464,6467,6467,6468,6470,6471,6472,6476,6477,6478,6478,6479,6481,6483,6483,6484,6484,6485,6486,6489,6489,6489,6489,6493,6495,6495,6495,6495,6497,6497,6498,6499,6499,6500,6501,6501,6502,6503,6506,6506,6506,6507,6512,6513,6515,6516,6522,6523,6523,6526,6527,6528,6530,6531,6531,6532,6533,6534,6534,6534,6535,6536,6537,6537,6537,6537,6538,6538,6541,6542,6542,6542,6542,6543,6543,6548,6549,6551,6551,6551,6553,6554,6556,6556,6556,6557,6558,6558,6559,6559,6560,6563,6564,6565,6566,6567,6569,6570,6571,6572,6572,6573,6574,6578,6579,6580,6581,6582,6582,6584,6584,6585,6585,6588,6589,6589,6592,6592,6593,6594,6596,6597,6597,6598,6599,6600,6601,6602,6602,6602,6603,6603,6605,6606,6609,6610,6611,6612,6614,6614,6615,6618,6618,6619,6620,6622,6624,6625,6627,6627,6629,6630,6632,6633,6634,6634,6635,6636,6636,6636,6637,6637,6638,6638,6638,6640,6640,6640,6642,6643,6643,6643,6644,6646,6646,6647,6648,6652,6652,6653,6655,6655,6656,6656,6658,6659,6659,6660,6661,6661,6662,6662,6663,6663,6665,6665,6667,6669,6670,6672,6673,6674,6674,6674,6674,6675,6676,6676,6677,6678,6679,6683,6684,6687,6688,6689,6689,6690,6691,6693,6693,6694,6695,6696,6697,6698,6699,6701,6702,6702,6703,6706,6706,6706,6707,6707,6707,6708,6712,6713,6714,6715,6715,6716,6716,6717,6717,6719,6720,6721,6722,6722,6723,6724,6725,6726,6727,6727,6728,6728,6729,6729,6730,6730,6734,6738,6738,6738,6740,6740,6743,6744,6744,6744,6746,6747,6748,6749,6751,6751,6752,6752,6755,6755,6756,6757,6757,6758,6758,6759,6761,6761,6761,6762,6763,6764,6765,6766,6766,6767,6767,6768,6769,6769,6770,6772,6773,6775,6776,6777,6778,6782,6782,6784,6785,6785,6785,6786,6786,6786,6787,6788,6788,6789,6790,6790,6791,6791,6792,6792,6792,6792,6792,6795,6796,6797,6798,6798,6799,6800,6800,6800,6802,6803,6804,6805,6806,6808,6808,6809,6809,6810,6810,6812,6812,6814,6815,6815,6816,6817,6818,6819,6820,6821,6821,6822,6823,6824,6825,6825,6826,6826,6826,6827,6827,6828,6829,6829,6830,6831,6833,6834,6835,6837,6838,6839,6840,6841,6842,6843,6843,6843,6844,6844,6845,6845,6846,6847,6847,6848,6848,6850,6850,6850,6850,6852,6852,6853,6853,6853,6854,6855,6856,6857,6858,6858,6859,6860,6860,6860,6863,6864,6864,6865,6865,6865,6865,6867,6869,6870,6870,6870,6871,6871,6872,6873,6874,6877,6877,6878,6879,6879,6883,6883,6884,6887,6888,6889,6891,6891,6892,6892,6892,6893,6893,6897,6899,6901,6901,6902,6903,6903,6903,6906,6906,6906,6910,6910,6910,6911,6911,6911,6912,6913,6913,6914,6917,6918,6919,6920,6920,6921,6924,6926,6927,6928,6931,6931,6931,6932,6932,6932,6934,6934,6940,6942,6942,6944,6944,6945,6947,6948,6950,6952,6953,6953,6953,6955,6955,6958,6958,6958,6959,6962,6963,6963,6964,6965,6966,6967,6967,6969,6971,6974,6975,6979,6979,6982,6984,6985,6990,6992,6993,6993,6996,6996,6996,6997,6998,7000,7000,7001,7002,7003,7003,7003,7004,7004,7004,7005,7005,7007,7009,7014,7015,7015,7018,7019,7020,7020,7021,7022,7023,7024,7026,7026,7026,7028,7028,7028,7029,7029,7029,7030,7030,7031,7033,7034,7035,7035,7035,7035,7035,7036,7037,7039,7039,7040,7043,7044,7045,7046,7048,7048,7049,7049,7050,7051,7055,7055,7057,7058,7060,7067,7068,7068,7070,7070,7070,7070,7070,7070,7071,7071,7072,7072,7072,7074,7079,7079,7080,7081,7082,7083,7083,7085,7086,7086,7086,7087,7087,7088,7089,7089,7091,7092,7092,7092,7093,7093,7094,7098,7099,7099,7100,7103,7104,7105,7107,7109,7111,7112,7115,7116,7119,7120,7120,7121,7121,7122,7122,7122,7123,7125,7125,7126,7126,7127,7129,7130,7130,7132,7132,7133,7134,7136,7137,7138,7139,7140,7141,7144,7145,7145,7146,7146,7146,7147,7149,7150,7150,7151,7151,7152,7153,7153,7154,7156,7157,7159,7159,7159,7160,7161,7162,7163,7164,7164,7166,7166,7167,7168,7169,7170,7171,7173,7177,7177,7178,7178,7179,7180,7182,7185,7188,7189,7191,7191,7191,7194,7195,7197,7197,7197,7198,7199,7199,7199,7200,7201,7205,7208,7209,7211,7212,7212,7214,7216,7218,7219,7219,7220,7220,7222,7222,7223,7225,7228,7228,7229,7231,7231,7232,7232,7232,7234,7235,7236,7236,7237,7237,7239,7240,7241,7242,7242,7242,7243,7243,7243,7245,7245,7245,7245,7246,7248,7248,7254,7256,7257,7258,7263,7264,7264,7267,7267,7267,7267,7268,7268,7270,7270,7271,7273,7276,7276,7277,7277,7278,7278,7279,7279,7280,7280,7281,7281,7281,7284,7284,7287,7288,7289,7290,7290,7291,7292,7292,7293,7293,7293,7295,7297,7298,7298,7299,7299,7299,7300,7300,7302,7303,7306,7306,7306,7308,7311,7311,7313,7313,7314,7315,7323,7324,7324,7326,7327,7327,7328,7329,7330,7332,7333,7335,7336,7337,7339,7339,7342,7343,7346,7347,7348,7350,7350,7352,7354,7355,7355,7356,7356,7356,7357,7357,7358,7358,7359,7359,7360,7362,7363,7363,7363,7363,7364,7368,7368,7370,7371,7371,7372,7372,7373,7374,7375,7375,7375,7375,7377,7377,7378,7380,7384,7385,7386,7388,7388,7389,7389,7391,7391,7392,7393,7394,7394,7395,7397,7400,7401,7402,7402,7402,7403,7404,7406,7408,7411,7412,7413,7414,7414,7415,7416,7416,7418,7419,7419,7420,7421,7424,7425,7425,7425,7425,7427,7428,7428,7429,7430,7430,7432,7432,7436,7436,7438,7439,7441,7441,7441,7443,7444,7445,7445,7449,7451,7452,7452,7453,7453,7454,7455,7456,7458,7461,7462,7462,7463,7464,7465,7466,7467,7467,7468,7469,7469,7469,7470,7471,7472,7472,7474,7475,7476,7477,7479,7480,7480,7483,7485,7486,7486,7486,7487,7488,7489,7490,7491,7496,7497,7497,7498,7502,7502,7510,7510,7516,7517,7518,7518,7520,7521,7521,7523,7524,7524,7525,7525,7525,7526,7527,7528,7529,7531,7532,7533,7533,7538,7541,7542,7543,7543,7547,7548,7548,7549,7552,7553,7553,7554,7554,7557,7562,7563,7564,7564,7566,7567,7568,7568,7569,7569,7572,7573,7573,7575,7576,7580,7581,7581,7582,7585,7585,7588,7588,7588,7589,7590,7591,7591,7592,7592,7592,7593,7596,7597,7597,7599,7601,7601,7602,7602,7604,7604,7606,7608,7608,7609,7610,7611,7611,7613,7613,7613,7614,7615,7615,7615,7616,7619,7619,7620,7620,7620,7621,7622,7622,7623,7623,7624,7625,7627,7629,7632,7633,7633,7633,7634,7637,7637,7637,7640,7644,7644,7644,7645,7646,7646,7647,7648,7648,7648,7649,7650,7651,7652,7653,7653,7654,7655,7656,7656,7657,7657,7658,7659,7660,7661,7662,7663,7664,7664,7665,7665,7666,7667,7667,7668,7668,7668,7670,7670,7672,7673,7673,7674,7674,7675,7675,7676,7678,7679,7680,7680,7680,7681,7682,7682,7682,7683,7686,7688,7688,7689,7689,7691,7692,7693,7694,7694,7695,7696,7697,7698,7699,7701,7701,7703,7707,7707,7707,7708,7709,7709,7710,7710,7711,7713,7715,7715,7716,7719,7722,7722,7723,7723,7724,7724,7724,7724,7725,7726,7728,7728,7728,7728,7729,7731,7731,7732,7732,7734,7735,7735,7735,7738,7739,7739,7739,7741,7742,7742,7743,7743,7743,7744,7744,7744,7746,7746,7748,7748,7748,7752,7753,7754,7755,7755,7759,7761,7765,7765,7765,7771,7774,7774,7777,7778,7779,7779,7782,7784,7784,7786,7791,7792,7793,7796,7798,7799,7800,7800,7803,7804,7805,7805,7805,7806,7809,7809,7809,7809,7810,7811,7811,7813,7814,7814,7816,7816,7816,7816,7816,7819,7820,7820,7821,7822,7823,7824,7825,7825,7825,7826,7827,7833,7833,7833,7836,7836,7836,7837,7839,7842,7843,7844,7845,7845,7848,7850,7851,7852,7852,7854,7854,7856,7857,7857,7858,7860,7862,7863,7864,7865,7866,7870,7870,7871,7872,7872,7872,7873,7876,7877,7878,7880,7881,7883,7883,7884,7885,7885,7886,7889,7889,7890,7891,7892,7892,7893,7893,7894,7894,7895,7897,7898,7899,7899,7899,7900,7901,7902,7903,7903,7907,7908,7909,7912,7912,7913,7915,7916,7916,7916,7917,7919,7920,7923,7924,7928,7928,7929,7929,7930,7931,7931,7932,7934,7935,7936,7937,7938,7938,7939,7940,7941,7942,7942,7942,7943,7944,7945,7946,7947,7948,7950,7950,7951,7951,7953,7955,7956,7956,7957,7958,7960,7963,7963,7966,7967,7967,7969,7969,7970,7970,7970,7971,7972,7974,7976,7976,7977,7978,7982,7984,7987,7987,7987,7988,7989,7991,7991,7992,7993,7994,7995,7996,7996,7996,7996,7997,7998,7998,7999,8000,8002,8002,8002,8003,8003,8004,8009,8010,8011,8012,8013,8013,8014,8015,8015,8016,8016,8017,8018,8019,8019,8019,8019,8021,8021,8021,8022,8026,8026,8026,8027,8027,8029,8031,8031,8032,8032,8033,8034,8035,8036,8037,8039,8039,8039,8041,8041,8042,8042,8043,8043,8043,8043,8044,8044,8044,8046,8047,8047,8051,8052,8052,8055,8056,8057,8057,8058,8059,8060,8061,8067,8067,8068,8068,8069,8071,8072,8075,8078,8080,8083,8085,8086,8087,8090,8090,8091,8093,8093,8095,8095,8095,8095,8096,8097,8098,8100,8100,8100,8102,8105,8105,8107,8108,8108,8109,8110,8111,8113,8113,8116,8117,8121,8122,8122,8123,8125,8125,8126,8126,8128,8129,8130,8130,8131,8134,8134,8135,8138,8139,8140,8141,8143,8144,8146,8147,8148,8148,8150,8151,8151,8151,8152,8153,8155,8157,8158,8163,8164,8167,8167,8168,8168,8169,8171,8172,8172,8173,8174,8174,8175,8176,8176,8176,8176,8176,8178,8180,8182,8183,8183,8185,8186,8186,8187,8187,8188,8188,8188,8189,8192,8192,8192,8194,8194,8195,8197,8197,8199,8200,8201,8201,8201,8202,8202,8204,8205,8205,8205,8205,8208,8210,8211,8212,8213,8213,8214,8215,8215,8217,8218,8218,8218,8219,8219,8220,8220,8220,8224,8226,8226,8226,8228,8232,8233,8234,8235,8240,8240,8241,8242,8242,8243,8248,8249,8249,8250,8250,8252,8252,8252,8254,8254,8255,8255,8255,8256,8256,8258,8259,8261,8262,8263,8264,8265,8266,8268,8268,8271,8271,8271,8272,8273,8275,8276,8277,8277,8278,8278,8279,8280,8281,8281,8281,8282,8284,8285,8285,8286,8288,8288,8289,8290,8290,8291,8292,8294,8294,8295,8296,8296,8298,8298,8302,8302,8302,8303,8303,8304,8305,8305,8305,8307,8307,8308,8309,8310,8310,8311,8312,8313,8314,8314,8316,8316,8319,8320,8324,8326,8326,8326,8328,8328,8328,8329,8330,8330,8330,8331,8331,8333,8333,8335,8336,8337,8342,8342,8342,8343,8344,8346,8347,8348,8349,8352,8353,8355,8355,8356,8358,8359,8360,8360,8362,8362,8364,8364,8364,8365,8365,8367,8368,8368,8368,8369,8370,8370,8372,8373,8374,8374,8376,8376,8378,8378,8379,8379,8379,8383,8384,8385,8386,8387,8389,8390,8390,8392,8393,8394,8394,8395,8395,8395,8395,8401,8401,8402,8402,8403,8406,8408,8408,8410,8410,8411,8412,8412,8414,8414,8416,8417,8418,8418,8419,8420,8420,8421,8423,8426,8426,8428,8428,8429,8431,8433,8434,8434,8437,8437,8438,8440,8443,8443,8445,8446,8446,8448,8452,8452,8453,8454,8455,8455,8456,8459,8459,8460,8463,8464,8465,8465,8465,8465,8467,8468,8469,8469,8470,8471,8471,8473,8473,8474,8476,8476,8478,8479,8480,8481,8481,8483,8483,8483,8484,8486,8487,8489,8490,8490,8490,8491,8493,8493,8493,8494,8497,8498,8499,8501,8502,8502,8503,8504,8504,8507,8508,8508,8509,8511,8511,8513,8515,8516,8516,8517,8519,8522,8522,8526,8528,8529,8530,8530,8530,8530,8530,8531,8533,8533,8533,8534,8535,8538,8539,8539,8540,8542,8543,8543,8544,8544,8545,8545,8548,8549,8550,8550,8551,8551,8552,8553,8554,8555,8556,8557,8560,8560,8560,8561,8562,8562,8565,8568,8569,8572,8573,8573,8575,8575,8575,8575,8577,8577,8577,8578,8578,8579,8579,8580,8582,8585,8587,8591,8593,8595,8596,8600,8601,8602,8603,8605,8605,8610,8610,8611,8612,8613,8614,8614,8615,8616,8618,8620,8620,8621,8621,8621,8622,8623,8623,8623,8627,8627,8628,8630,8630,8632,8632,8633,8633,8633,8634,8635,8635,8635,8636,8637,8638,8640,8640,8641,8642,8642,8642,8645,8646,8646,8646,8646,8647,8647,8647,8647,8651,8654,8654,8656,8657,8659,8659,8660,8660,8660,8661,8662,8664,8667,8670,8670,8672,8672,8673,8674,8675,8679,8679,8679,8683,8685,8687,8687,8688,8689,8690,8691,8691,8691,8691,8692,8692,8692,8693,8694,8695,8696,8697,8700,8701,8703,8703,8704,8704,8704,8705,8707,8708,8708,8709,8709,8710,8712,8712,8713,8713,8714,8714,8714,8716,8716,8717,8720,8723,8723,8723,8724,8724,8725,8726,8728,8729,8730,8733,8734,8734,8736,8737,8738,8739,8739,8740,8744,8745,8745,8746,8749,8749,8749,8750,8753,8753,8754,8755,8756,8757,8760,8761,8762,8763,8765,8766,8766,8766,8768,8768,8769,8770,8771,8771,8772,8773,8774,8776,8776,8777,8777,8778,8779,8783,8784,8784,8784,8785,8786,8787,8788,8789,8791,8794,8795,8795,8796,8796,8798,8798,8798,8798,8800,8805,8808,8811,8811,8811,8812,8812,8814,8815,8815,8816,8817,8817,8818,8818,8818,8821,8822,8822,8822,8823,8824,8824,8824,8827,8828,8829,8831,8831,8831,8832,8833,8833,8833,8833,8834,8835,8836,8836,8836,8841,8843,8843,8845,8847,8847,8848,8849,8849,8849,8849,8850,8850,8850,8851,8851,8852,8852,8852,8853,8854,8854,8854,8857,8859,8860,8860,8863,8863,8864,8865,8865,8865,8866,8867,8870,8870,8870,8871,8872,8872,8873,8873,8874,8874,8874,8876,8878,8879,8880,8882,8884,8884,8885,8886,8887,8887,8889,8889,8891,8891,8891,8892,8895,8896,8896,8897,8899,8901,8901,8902,8902,8902,8904,8905,8905,8905,8905,8908,8911,8911,8911,8912,8912,8912,8914,8914,8914,8916,8916,8916,8920,8920,8921,8921,8922,8924,8924,8928,8928,8929,8930,8930,8931,8932,8932,8933,8933,8934,8935,8935,8936,8937,8937,8939,8940,8941,8942,8943,8944,8944,8944,8945,8945,8946,8946,8947,8948,8948,8949,8951,8952,8953,8953,8954,8955,8955,8955,8956,8956,8956,8957,8958,8958,8958,8959,8961,8961,8961,8961,8962,8963,8963,8964,8965,8965,8966,8966,8967,8969,8970,8972,8973,8973,8973,8976,8977,8977,8979,8980,8981,8981,8984,8984,8987,8987,8988,8989,8990,8991,8995,8995,8996,8998,9001,9010,9011,9011,9011,9012,9013,9014,9017,9018,9019,9021,9021,9021,9022,9024,9026,9028,9029,9029,9029,9031,9032,9034,9035,9036,9036,9037,9037,9040,9043,9044,9044,9044,9045,9046,9046,9047,9047,9047,9049,9049,9050,9051,9052,9053,9053,9056,9059,9060,9061,9063,9063,9065,9065,9065,9067,9068,9069,9070,9072,9074,9074,9076,9077,9077,9078,9078,9079,9082,9084,9085,9085,9086,9087,9088,9088,9092,9093,9096,9097,9097,9100,9100,9102,9103,9104,9105,9106,9109,9111,9111,9112,9115,9115,9116,9117,9117,9119,9119,9120,9122,9125,9128,9128,9128,9129,9129,9129,9132,9132,9132,9134,9134,9134,9135,9136,9137,9137,9138,9138,9138,9139,9140,9140,9141,9142,9143,9143,9146,9146,9147,9148,9150,9151,9152,9152,9153,9153,9153,9154,9156,9156,9157,9157,9158,9161,9161,9162,9162,9163,9164,9164,9164,9166,9166,9166,9167,9168,9169,9170,9171,9171,9172,9176,9176,9176,9177,9179,9179,9180,9181,9183,9183,9185,9188,9189,9190,9192,9192,9193,9193,9193,9193,9195,9196,9197,9198,9198,9198,9199,9201,9201,9201,9204,9205,9206,9209,9210,9211,9211,9212,9213,9214,9214,9214,9214,9215,9217,9218,9219,9219,9219,9221,9221,9222,9224,9225,9225,9226,9227,9227,9228,9229,9229,9230,9231,9231,9232,9237,9238,9238,9239,9239,9241,9241,9241,9241,9244,9244,9246,9247,9248,9251,9252,9252,9252,9252,9254,9254,9257,9260,9260,9262,9264,9264,9264,9265,9265,9265,9265,9268,9268,9269,9270,9272,9272,9273,9274,9275,9275,9276,9278,9278,9278,9279,9280,9280,9282,9283,9286,9287,9287,9288,9289,9289,9289,9290,9292,9293,9293,9294,9294,9294,9295,9295,9296,9298,9298,9299,9300,9302,9303,9303,9304,9304,9304,9304,9306,9307,9308,9309,9309,9309,9309,9310,9311,9312,9313,9315,9317,9319,9319,9320,9321,9322,9324,9324,9327,9327,9328,9330,9330,9331,9333,9335,9336,9338,9338,9338,9339,9339,9340,9340,9342,9345,9345,9346,9346,9348,9350,9350,9351,9351,9351,9354,9355,9357,9360,9360,9360,9361,9362,9367,9367,9367,9367,9371,9371,9372,9372,9374,9375,9376,9376,9377,9378,9378,9378,9378,9378,9378,9380,9380,9380,9381,9382,9382,9383,9385,9386,9387,9387,9394,9395,9396,9397,9399,9399,9402,9404,9404,9405,9406,9408,9410,9410,9412,9412,9412,9413,9414,9414,9416,9417,9418,9419,9419,9420,9421,9421,9422,9423,9424,9424,9425,9425,9431,9431,9431,9432,9432,9434,9435,9436,9437,9438,9438,9440,9440,9440,9440,9441,9442,9445,9446,9446,9447,9449,9450,9451,9451,9451,9452,9452,9453,9454,9455,9455,9455,9455,9456,9460,9461,9461,9462,9462,9463,9466,9467,9470,9472,9473,9475,9477,9477,9479,9479,9479,9484,9485,9485,9486,9487,9489,9492,9492,9494,9497,9498,9498,9498,9500,9500,9501,9503,9504,9505,9507,9507,9507,9509,9509,9509,9511,9512,9513,9516,9517,9520,9521,9524,9524,9525,9525,9527,9528,9528,9528,9529,9531,9532,9533,9534,9535,9536,9537,9537,9540,9540,9540,9542,9543,9543,9544,9546,9549,9550,9551,9551,9555,9556,9556,9557,9560,9561,9563,9563,9564,9564,9565,9566,9566,9569,9570,9571,9574,9574,9574,9575,9576,9577,9579,9580,9580,9581,9584,9584,9585,9585,9585,9588,9588,9589,9589,9591,9592,9592,9592,9593,9595,9596,9596,9598,9599,9600,9601,9601,9601,9601,9602,9602,9604,9606,9606,9606,9608,9608,9609,9609,9609,9610,9610,9612,9614,9615,9616,9617,9618,9619,9619,9622,9626,9629,9630,9630,9635,9635,9636,9638,9638,9639,9639,9640,9642,9643,9643,9643,9643,9644,9645,9645,9646,9647,9649,9649,9651,9652,9653,9654,9656,9657,9658,9660,9661,9662,9663,9663,9664,9665,9668,9668,9668,9674,9674,9674,9674,9675,9675,9675,9675,9677,9678,9678,9678,9679,9679,9680,9682,9682,9683,9683,9685,9685,9687,9687,9687,9689,9689,9691,9692,9692,9692,9694,9695,9696,9696,9698,9699,9699,9702,9703,9703,9708,9708,9709,9711,9713,9714,9715,9715,9716,9717,9718,9718,9720,9723,9723,9723,9724,9725,9726,9726,9727,9728,9729,9729,9729,9729,9729,9734,9735,9738,9738,9742,9743,9744,9745,9745,9745,9746,9747,9747,9748,9748,9749,9749,9749,9750,9752,9753,9755,9755,9757,9759,9759,9760,9762,9762,9765,9765,9767,9767,9768,9768,9768,9772,9774,9774,9774,9775,9776,9779,9779,9779,9780,9781,9781,9782,9782,9782,9783,9784,9785,9788,9789,9790,9790,9791,9792,9794,9794,9795,9796,9797,9797,9797,9798,9798,9799,9801,9801,9803,9803,9805,9806,9807,9809,9810,9811,9811,9812,9813,9813,9814,9815,9815,9816,9818,9819,9821,9828,9828,9828,9830,9833,9833,9834,9837,9838,9838,9839,9841,9841,9843,9847,9848,9848,9849,9853,9853,9858,9860,9861,9861,9861,9862,9862,9863,9863,9863,9864,9865,9867,9868,9872,9873,9873,9874,9875,9875,9876,9876,9880,9880,9881,9883,9884,9884,9885,9885,9885,9885,9886,9886,9886,9888,9890,9892,9892,9894,9894,9895,9896,9897,9897,9898,9898,9901,9902,9902,9902,9902,9903,9905,9906,9908,9909,9910,9911,9911,9912,9916,9916,9919,9919,9919,9919,9920,9920,9920,9920,9921,9921,9921,9925,9925,9926,9928,9929,9929,9930,9930,9930,9931,9931,9931,9933,9938,9939,9940,9940,9942,9942,9942,9943,9943,9944,9945,9945,9946,9946,9948,9949,9949,9949,9949,9950,9950,9952,9952,9952,9953,9954,9956,9958,9958,9959,9959,9959,9959,9959,9960,9961,9962,9962,9963,9964,9964,9966,9967,9968,9968,9971,9971,9972,9972,9972,9972,9973,9973,6974,9975,9975,9976,9978,9978,978,9979,9979,9980,9781,9981,8981,9981,9985,1986,99,9987,9688,9989,9989,9989,9992,7992,9993,9994,9914,9995,9995,9998};
clock_t start = clock(); 
    quickSort(a,0,n);
    cout <<"Sorted Array: " << endl;
    	  clock_t end = clock(); 
    double time = double(end - start) / CLOCKS_PER_SEC; 
    cout<<"Time consumed = "<<time<<" sec"<<endl;

    for(int i=0;i<n;i++)
    {
    	cout <<a[i] <<",";
	}
}