[LeetCode] #236. Lowest Common Ancestor of a Binary Tree

題目

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

直覺解

構想：

1. 把 Tree 轉成 array，index 為 k 的元素，其子元素 index 為 2k+1 和 2k+2，其父元素 index 為 k-1 / 2 後無條件捨去到整數位

2. 找出 p 和 q 在 array 中的 index

3. 找出 p 和 q 的所有 ancestor，在 array 中的 index

4. 找出 lowest common ancestor

python 3 實作（失敗）：

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': 

    heap = [root] 

    children_unchecked = [root] 

    p_index = None 

    q_index = None 

    isDone = False 

    # 把 Tree 轉成 array 

    while not isDone: 

        isDone = True 

        temp = [] 

        for node in children_unchecked: 

            if node: 

                temp.extend([node.left, node.right]) 

                if node.left or node.right: 

                    isDone = False 

            else: 

                temp.extend([None, None]) 

                     

        if not isDone: 

            heap.extend(temp) 

            children_unchecked = temp 

   

    # 找出 p 和 q 在 array 中的 index 

    for index, node in enumerate(heap): 

        if not node: 

            continue 

        if node.val == p.val: 

            p_index = index 

        elif node.val == q.val: 

            q_index = index 

         

    # 找出 p 和 q 的所有 ancestor，在 array 中的 index 

    p_ancestor_index = [p_index] 

    q_ancestor_index = [q_index] 

    isDone = False 

    while not isDone: 

        isDone = True 

        parent_index = (p_index - 1) // 2 

        p_index = parent_index 

        if parent_index >= 0: 

            p_ancestor_index.append(parent_index) 

            isDone = False 

        parent_index = (q_index - 1) // 2 

        q_index = parent_index 

        if parent_index >= 0: 

             q_ancestor_index.append(parent_index) 

            isDone = False 

 

    # 找出 lowest common ancestor 

    high_ancestor_index = p_ancestor_index if p_ancestor_index[0] < q_ancestor_index[0] else q_ancestor_index 

    low_ancestor_index = q_ancestor_index if high_ancestor_index is p_ancestor_index else p_ancestor_index 

    for index in low_ancestor_index: 

        if index in high_ancestor_index: 

            return heap[index]

錯誤：Time Limit Exceeded

29 / 31 test cases passed.

Last executed input:

root: （大概是一顆只長左邊分枝的樹，跟 linked list 差不多）
[-1,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10,null,11,null,12,null,13,null,14,null,15,null,16,null,17,null,18,null,19,null,20,null,21,null,22,null,23,null,24,null,25,null,26,null,27,null,28,null,29,null,30,null,31,null,32,null,33,null,34,null,35,null,36,null,37,null,38,null,39,null,40,null,41,null,42,null,43,null,44,null,45,null,46,null,47,null,48,null,49,null,50,null,51,null,52,null,53,null,54,null,55,null,56,null,57,null,58,null,59,null,60,null,61,null,62,null,63,null,64,null,65,null,66,null,67,null,68,null,69,null,70,null,71,null,72,null,73,null,74,null,75,null,76,null,77,null,78,null,79,null,80,null,81,null,82,null,83,null,84,null,85,null,86,null,87,null,88,null,89,null,90,null,91,null,92,null,93,null,94,null,95,null,96,null,97,null,98,null,99,null,100,null,101,null,102,null,103,null,104,null,105,null,106,null,107,null,108,null,109,null,110,null,111,null,112,null,113,null,114,null,115,null,116,null,117,null,118,null,119,null,120,null,121,null,122,null,123,null,124,null,125,null,126,null,127,null,128,null,129,null,130,null,131,null,132,null,133,null,134,null,135,null,136,null,137,null,138,null,139,null,140,null,141,null,142,null,143,null,144,null,145,null,146,null,147,null,148,null,149,null,150,null,151,null,152,null,153,null,154,null,155,null,156,null,157,null,158,null,159,null,160,null,161,null,162,null,163,null,164,null,165,null,166,null,167,null,168,null,169,null,170,null,171,null,172,null,173,null,174,null,175,null,176,null,177,null,178,null,179,null,180,null,181,null,182,null,183,null,184,null,185,null,186,null,187,null,188,null,189,null,190,null,191,null,192,null,193,null,194,null,195,null,196,null,197,null,198,null,199,null,200,null,201,null,202,null,203,null,204,null,205,null,206,null,207,null,208,null,209,null,210,null,211,null,212,null,213,null,214,null,215,null,216,null,217,null,218,null,219,null,220,null,221,null,222,null,223,null,224,null,225,null,226,null,227,null,228,null,229,null,230,null,231,null,232,null,233,null,234,null,235,null,236,null,237,null,238,null,239,null,240,null,241,null,242,null,243,null,244,null,245,null,246,null,247,null,248,null,249,null,250,null,251,null,252,null,253,null,254,null,255,null,256,null,257,null,258,null,259,null,260,null,261,null,262,null,263,null,264,null,265,null,266,null,267,null,268,null,269,null,270,null,271,null,272,null,273,null,274,null,275,null,276,null,277,null,278,null,279,null,280,null,281,null,282,null,283,null,284,null,285,null,286,null,287,null,288,null,289,null,290,null,291,null,292,null,293,null,294,null,295,null,296,null,297,null,298,null,299,null,300,null,301,null,302,null,303,null,304,null,305,null,306,null,307,null,308,null,309,null,310,null,311,null,312,null,313,null,314,null,315,null,316,null,317,null,318,null,319,null,320,null,321,null,322,null,323,null,324,null,325,null,326,null,327,null,328,null,329,null,330,null,331,null,332,null,333,null,334,null,335,null,336,null,337,null,338,null,339,null,340,null,341,null,342,null,343,null,344,null,345,null,346,null,347,null,348,null,349,null,350,null,351,null,352,null,353,null,354,null,355,null,356,null,357,null,358,null,359,null,360,null,361,null,362,null,363,null,364,null,365,null,366,null,367,null,368,null,369,null,370,null,371,null,372,null,373,null,374,null,375,null,376,null,377,null,378,null,379,null,380,null,381,null,382,null,383,null,384,null,385,null,386,null,387,null,388,null,389,null,390,null,391,null,392,null,393,null,394,null,395,null,396,null,397,null,398,null,399,null,400,null,401,null,402,null,403,null,404,null,405,null,406,null,407,null,408,null,409,null,410,null,411,null,412,null,413,null,414,null,415,null,416,null,417,null,418,null,419,null,420,null,421,null,422,null,423,null,424,null,425,null,426,null,427,null,428,null,429,null,430,null,431,null,432,null,433,null,434,null,435,null,436,null,437,null,438,null,439,null,440,null,441,null,442,null,443,null,444,null,445,null,446,null,447,null,448,null,449,null,450,null,451,null,452,null,453,null,454,null,455,null,456,null,457,null,458,null,459,null,460,null,461,null,462,null,463,null,464,null,465,null,466,null,467,null,468,null,469,null,470,null,471,null,472,null,473,null,474,null,475,null,476,null,477,null,478,null,479,null,480,null,481,null,482,null,483,null,484,null,485,null,486,null,487,null,488,null,489,null,490,null,491,null,492,null,493,null,494,null,495,null,496,null,497,null,498,null,499,null,500,null,501,null,502,null,503,null,504,null,505,null,506,null,507,null,508,null,509,null,510,null,511,null,512,null,513,null,514,null,515,null,516,null,517,null,518,null,519,null,520,null,521,null,522,null,523,null,524,null,525,null,526,null,527,null,528,null,529,null,530,null,531,null,532,null,533,null,534,null,535,null,536,null,537,null,538,null,539,null,540,null,541,null,542,null,543,null,544,null,545,null,546,null,547,null,548,null,549,null,550,null,551,null,552,null,553,null,554,null,555,null,556,null,557,null,558,null,559,null,560,null,561,null,562,null,563,null,564,null,565,null,566,null,567,null,568,null,569,null,570,null,571,null,572,null,573,null,574,null,575,null,576,null,577,null,578,null,579,null,580,null,581,null,582,null,583,null,584,null,585,null,586,null,587,null,588,null,589,null,590,null,591,null,592,null,593,null,594,null,595,null,596,null,597,null,598,null,599,null,600,null,601,null,602,null,603,null,604,null,605,null,606,null,607,null,608,null,609,null,610,null,611,null,612,null,613,null,614,null,615,null,616,null,617,null,618,null,619,null,620,null,621,null,622,null,623,null,624,null,625,null,626,null,627,null,628,null,629,null,630,null,631,null,632,null,633,null,634,null,635,null,636,null,637,null,638,null,639,null,640,null,641,null,642,null,643,null,644,null,645,null,646,null,647,null,648,null,649,null,650,null,651,null,652,null,653,null,654,null,655,null,656,null,657,null,658,null,659,null,660,null,661,null,662,null,663,null,664,null,665,null,666,null,667,null,668,null,669,null,670,null,671,null,672,null,673,null,674,null,675,null,676,null,677,null,678,null,679,null,680,null,681,null,682,null,683,null,684,null,685,null,686,null,687,null,688,null,689,null,690,null,691,null,692,null,693,null,694,null,695,null,696,null,697,null,698,null,699,null,700,null,701,null,702,null,703,null,704,null,705,null,706,null,707,null,708,null,709,null,710,null,711,null,712,null,713,null,714,null,715,null,716,null,717,null,718,null,719,null,720,null,721,null,722,null,723,null,724,null,725,null,726,null,727,null,728,null,729,null,730,null,731,null,732,null,733,null,734,null,735,null,736,null,737,null,738,null,739,null,740,null,741,null,742,null,743,null,744,null,745,null,746,null,747,null,748,null,749,null,750,null,751,null,752,null,753,null,754,null,755,null,756,null,757,null,758,null,759,null,760,null,761,null,762,null,763,null,764,null,765,null,766,null,767,null,768,null,769,null,770,null,771,null,772,null,773,null,774,null,775,null,776,null,777,null,778,null,779,null,780,null,781,null,782,null,783,null,784,null,785,null,786,null,787,null,788,null,789,null,790,null,791,null,792,null,793,null,794,null,795,null,796,null,797,null,798,null,799,null,800,null,801,null,802,null,803,null,804,null,805,null,806,null,807,null,808,null,809,null,810,null,811,null,812,null,813,null,814,null,815,null,816,null,817,null,818,null,819,null,820,null,821,null,822,null,823,null,824,null,825,null,826,null,827,null,828,null,829,null,830,null,831,null,832,null,833,null,834,null,835,null,836,null,837,null,838,null,839,null,840,null,841,null,842,null,843,null,844,null,845,null,846,null,847,null,848,null,849,null,850,null,851,null,852,null,853,null,854,null,855,null,856,null,857,null,858,null,859,null,860,null,861,null,862,null,863,null,864,null,865,null,866,null,867,null,868,null,869,null,870,null,871,null,872,null,873,null,874,null,875,null,876,null,877,null,878,null,879,null,880,null,881,null,882,null,883,null,884,null,885,null,886,null,887,null,888,null,889,null,890,null,891,null,892,null,893,null,894,null,895,null,896,null,897,null,898,null,899,null,900,null,901,null,902,null,903,null,904,null,905,null,906,null,907,null,908,null,909,null,910,null,911,null,912,null,913,null,914,null,915,null,916,null,917,null,918,null,919,null,920,null,921,null,922,null,923,null,924,null,925,null,926,null,927,null,928,null,929,null,930,null,931,null,932,null,933,null,934,null,935,null,936,null,937,null,938,null,939,null,940,null,941,null,942,null,943,null,944,null,945,null,946,null,947,null,948,null,949,null,950,null,951,null,952,null,953,null,954,null,955,null,956,null,957,null,958,null,959,null,960,null,961,null,962,null,963,null,964,null,965,null,966,null,967,null,968,null,969,null,970,null,971,null,972,null,973,null,974,null,975,null,976,null,977,null,978,null,979,null,980,null,981,null,982,null,983,null,984,null,985,null,986,null,987,null,988,null,989,null,990,null,991,null,992,null,993,null,994,null,995,null,996,null,997,null,998,null,999,null,1000,null,1001,null,1002,null,1003,null,1004,null,1005,null,1006,null,1007,null,1008,null,1009,null,1010,null,1011,null,1012,null,1013,null,1014,null,1015,null,1016,null,1017,null,1018,null,1019,null,1020,null,1021,null,1022,null,1023,null,1024,null,1025,null,1026,null,1027,null,1028,null,1029,null,1030,null,1031,null,1032,null,1033,null,1034,null,1035,null,1036,null,1037,null,1038,null,1039,null,1040,null,1041,null,1042,null,1043,null,1044,null,1045,null,1046,null,1047,null,1048,null,1049,null,1050,null,1051,null,1052,null,1053,null,1054,null,1055,null,1056,null,1057,null,1058,null,1059,null,1060,null,1061,null,1062,null,1063,null,1064,null,1065,null,1066,null,1067,null,1068,null,1069,null,1070,null,1071,null,1072,null,1073,null,1074,null,1075,null,1076,null,1077,null,1078,null,1079,null,1080,null,1081,null,1082,null,1083,null,1084,null,1085,null,1086,null,1087,null,1088,null,1089,null,1090,null,1091,null,1092,null,1093,null,1094,null,1095,null,1096,null,1097,null,1098,null,1099,null,1100,null,1101,null,1102,null,1103,null,1104,null,1105,null,1106,null,1107,null,1108,null,1109,null,1110,null,1111,null,1112,null,1113,null,1114,null,1115,null,1116,null,1117,null,1118,null,1119,null,1120,null,1121,null,1122,null,1123,null,1124,null,1125,null,1126,null,1127,null,1128,null,1129,null,1130,null,1131,null,1132,null,1133,null,1134,null,1135,null,1136,null,1137,null,1138,null,1139,null,1140,null,1141,null,1142,null,1143,null,1144,null,1145,null,1146,null,1147,null,1148,null,1149,null,1150,null,1151,null,1152,null,1153,null,1154,null,1155,null,1156,null,1157,null,1158,null,1159,null,1160,null,1161,null,1162,null,1163,null,1164,null,1165,null,1166,null,1167,null,1168,null,1169,null,1170,null,1171,null,1172,null,1173,null,1174,null,1175,null,1176,null,1177,null,1178,null,1179,null,1180,null,1181,null,1182,null,1183,null,1184,null,1185,null,1186,null,1187,null,1188,null,1189,null,1190,null,1191,null,1192,null,1193,null,1194,null,1195,null,1196,null,1197,null,1198,null,1199,null,1200,null,1201,null,1202,null,1203,null,1204,null,1205,null,1206,null,1207,null,1208,null,1209,null,1210,null,1211,null,1212,null,1213,null,1214,null,1215,null,1216,null,1217,null,1218,null,1219,null,1220,null,1221,null,1222,null,1223,null,1224,null,1225,null,1226,null,1227,null,1228,null,1229,null,1230,null,1231,null,1232,null,1233,null,1234,null,1235,null,1236,null,1237,null,1238,null,1239,null,1240,null,1241,null,1242,null,1243,null,1244,null,1245,null,1246,null,1247,null,1248,null,1249,null,1250,null,1251,null,1252,null,1253,null,1254,null,1255,null,1256,null,1257,null,1258,null,1259,null,1260,null,1261,null,1262,null,1263,null,1264,null,1265,null,1266,null,1267,null,1268,null,1269,null,1270,null,1271,null,1272,null,1273,null,1274,null,1275,null,1276,null,1277,null,1278,null,1279,null,1280,null,1281,null,1282,null,1283,null,1284,null,1285,null,1286,null,1287,null,1288,null,1289,null,1290,null,1291,null,1292,null,1293,null,1294,null,1295,null,1296,null,1297,null,1298,null,1299,null,1300,null,1301,null,1302,null,1303,null,1304,null,1305,null,1306,null,1307,null,1308,null,1309,null,1310,null,1311,null,1312,null,1313,null,1314,null,1315,null,1316,null,1317,null,1318,null,1319,null,1320,null,1321,null,1322,null,1323,null,1324,null,1325,null,1326,null,1327,null,1328,null,1329,null,1330,null,1331,null,1332,null,1333,null,1334,null,1335,null,1336,null,1337,null,1338,null,1339,null,1340,null,1341,null,1342,null,1343,null,1344,null,1345,null,1346,null,1347,null,1348,null,1349,null,1350,null,1351,null,1352,null,1353,null,1354,null,1355,null,1356,null,1357,null,1358,null,1359,null,1360,null,1361,null,1362,null,1363,null,1364,null,1365,null,1366,null,1367,null,1368,null,1369,null,1370,null,1371,null,1372,null,1373,null,1374,null,1375,null,1376,null,1377,null,1378,null,1379,null,1380,null,1381,null,1382,null,1383,null,1384,null,1385,null,1386,null,1387,null,1388,null,1389,null,1390,null,1391,null,1392,null,1393,null,1394,null,1395,null,1396,null,1397,null,1398,null,1399,null,1400,null,1401,null,1402,null,1403,null,1404,null,1405,null,1406,null,1407,null,1408,null,1409,null,1410,null,1411,null,1412,null,1413,null,1414,null,1415,null,1416,null,1417,null,1418,null,1419,null,1420,null,1421,null,1422,null,1423,null,1424,null,1425,null,1426,null,1427,null,1428,null,1429,null,1430,null,1431,null,1432,null,1433,null,1434,null,1435,null,1436,null,1437,null,1438,null,1439,null,1440,null,1441,null,1442,null,1443,null,1444,null,1445,null,1446,null,1447,null,1448,null,1449,null,1450,null,1451,null,1452,null,1453,null,1454,null,1455,null,1456,null,1457,null,1458,null,1459,null,1460,null,1461,null,1462,null,1463,null,1464,null,1465,null,1466,null,1467,null,1468,null,1469,null,1470,null,1471,null,1472,null,1473,null,1474,null,1475,null,1476,null,1477,null,1478,null,1479,null,1480,null,1481,null,1482,null,1483,null,1484,null,1485,null,1486,null,1487,null,1488,null,1489,null,1490,null,1491,null,1492,null,1493,null,1494,null,1495,null,1496,null,1497,null,1498,null,1499,null,1500,null,1501,null,1502,null,1503,null,1504,null,1505,null,1506,null,1507,null,1508,null,1509,null,1510,null,1511,null,1512,null,1513,null,1514,null,1515,null,1516,null,1517,null,1518,null,1519,null,1520,null,1521,null,1522,null,1523,null,1524,null,1525,null,1526,null,1527,null,1528,null,1529,null,1530,null,1531,null,1532,null,1533,null,1534,null,1535,null,1536,null,1537,null,1538,null,1539,null,1540,null,1541,null,1542,null,1543,null,1544,null,1545,null,1546,null,1547,null,1548,null,1549,null,1550,null,1551,null,1552,null,1553,null,1554,null,1555,null,1556,null,1557,null,1558,null,1559,null,1560,null,1561,null,1562,null,1563,null,1564,null,1565,null,1566,null,1567,null,1568,null,1569,null,1570,null,1571,null,1572,null,1573,null,1574,null,1575,null,1576,null,1577,null,1578,null,1579,null,1580,null,1581,null,1582,null,1583,null,1584,null,1585,null,1586,null,1587,null,1588,null,1589,null,1590,null,1591,null,1592,null,1593,null,1594,null,1595,null,1596,null,1597,null,1598,null,1599,null,1600,null,1601,null,1602,null,1603,null,1604,null,1605,null,1606,null,1607,null,1608,null,1609,null,1610,null,1611,null,1612,null,1613,null,1614,null,1615,null,1616,null,1617,null,1618,null,1619,null,1620,null,1621,null,1622,null,1623,null,1624,null,1625,null,1626,null,1627,null,1628,null,1629,null,1630,null,1631,null,1632,null,1633,null,1634,null,1635,null,1636,null,1637,null,1638,null,1639,null,1640,null,1641,null,1642,null,1643,null,1644,null,1645,null,1646,null,1647,null,1648,null,1649,null,1650,null,1651,null,1652,null,1653,null,1654,null,1655,null,1656,null,1657,null,1658,null,1659,null,1660,null,1661,null,1662,null,1663,null,1664,null,1665,null,1666,null,1667,null,1668,null,1669,null,1670,null,1671,null,1672,null,1673,null,1674,null,1675,null,1676,null,1677,null,1678,null,1679,null,1680,null,1681,null,1682,null,1683,null,1684,null,1685,null,1686,null,1687,null,1688,null,1689,null,1690,null,1691,null,1692,null,1693,null,1694,null,1695,null,1696,null,1697,null,1698,null,1699,null,1700,null,1701,null,1702,null,1703,null,1704,null,1705,null,1706,null,1707,null,1708,null,1709,null,1710,null,1711,null,1712,null,1713,null,1714,null,1715,null,1716,null,1717,null,1718,null,1719,null,1720,null,1721,null,1722,null,1723,null,1724,null,1725,null,1726,null,1727,null,1728,null,1729,null,1730,null,1731,null,1732,null,1733,null,1734,null,1735,null,1736,null,1737,null,1738,null,1739,null,1740,null,1741,null,1742,null,1743,null,1744,null,1745,null,1746,null,1747,null,1748,null,1749,null,1750,null,1751,null,1752,null,1753,null,1754,null,1755,null,1756,null,1757,null,1758,null,1759,null,1760,null,1761,null,1762,null,1763,null,1764,null,1765,null,1766,null,1767,null,1768,null,1769,null,1770,null,1771,null,1772,null,1773,null,1774,null,1775,null,1776,null,1777,null,1778,null,1779,null,1780,null,1781,null,1782,null,1783,null,1784,null,1785,null,1786,null,1787,null,1788,null,1789,null,1790,null,1791,null,1792,null,1793,null,1794,null,1795,null,1796,null,1797,null,1798,null,1799,null,1800,null,1801,null,1802,null,1803,null,1804,null,1805,null,1806,null,1807,null,1808,null,1809,null,1810,null,1811,null,1812,null,1813,null,1814,null,1815,null,1816,null,1817,null,1818,null,1819,null,1820,null,1821,null,1822,null,1823,null,1824,null,1825,null,1826,null,1827,null,1828,null,1829,null,1830,null,1831,null,1832,null,1833,null,1834,null,1835,null,1836,null,1837,null,1838,null,1839,null,1840,null,1841,null,1842,null,1843,null,1844,null,1845,null,1846,null,1847,null,1848,null,1849,null,1850,null,1851,null,1852,null,1853,null,1854,null,1855,null,1856,null,1857,null,1858,null,1859,null,1860,null,1861,null,1862,null,1863,null,1864,null,1865,null,1866,null,1867,null,1868,null,1869,null,1870,null,1871,null,1872,null,1873,null,1874,null,1875,null,1876,null,1877,null,1878,null,1879,null,1880,null,1881,null,1882,null,1883,null,1884,null,1885,null,1886,null,1887,null,1888,null,1889,null,1890,null,1891,null,1892,null,1893,null,1894,null,1895,null,1896,null,1897,null,1898,null,1899,null,1900,null,1901,null,1902,null,1903,null,1904,null,1905,null,1906,null,1907,null,1908,null,1909,null,1910,null,1911,null,1912,null,1913,null,1914,null,1915,null,1916,null,1917,null,1918,null,1919,null,1920,null,1921,null,1922,null,1923,null,1924,null,1925,null,1926,null,1927,null,1928,null,1929,null,1930,null,1931,null,1932,null,1933,null,1934,null,1935,null,1936,null,1937,null,1938,null,1939,null,1940,null,1941,null,1942,null,1943,null,1944,null,1945,null,1946,null,1947,null,1948,null,1949,null,1950,null,1951,null,1952,null,1953,null,1954,null,1955,null,1956,null,1957,null,1958,null,1959,null,1960,null,1961,null,1962,null,1963,null,1964,null,1965,null,1966,null,1967,null,1968,null,1969,null,1970,null,1971,null,1972,null,1973,null,1974,null,1975,null,1976,null,1977,null,1978,null,1979,null,1980,null,1981,null,1982,null,1983,null,1984,null,1985,null,1986,null,1987,null,1988,null,1989,null,1990,null,1991,null,1992,null,1993,null,1994,null,1995,null,1996,null,1997,null,1998,null,1999,null,2000,null,2001,null,2002,null,2003,null,2004,null,2005,null,2006,null,2007,null,2008,null,2009,null,2010,null,2011,null,2012,null,2013,null,2014,null,2015,null,2016,null,2017,null,2018,null,2019,null,2020,null,2021,null,2022,null,2023,null,2024,null,2025,null,2026,null,2027,null,2028,null,2029,null,2030,null,2031,null,2032,null,2033,null,2034,null,2035,null,2036,null,2037,null,2038,null,2039,null,2040,null,2041,null,2042,null,2043,null,2044,null,2045,null,2046,null,2047,null,2048,null,2049,null,2050,null,2051,null,2052,null,2053,null,2054,null,2055,null,2056,null,2057,null,2058,null,2059,null,2060,null,2061,null,2062,null,2063,null,2064,null,2065,null,2066,null,2067,null,2068,null,2069,null,2070,null,2071,null,2072,null,2073,null,2074,null,2075,null,2076,null,2077,null,2078,null,2079,null,2080,null,2081,null,2082,null,2083,null,2084,null,2085,null,2086,null,2087,null,2088,null,2089,null,2090,null,2091,null,2092,null,2093,null,2094,null,2095,null,2096,null,2097,null,2098,null,2099,null,2100,null,2101,null,2102,null,2103,null,2104,null,2105,null,2106,null,2107,null,2108,null,2109,null,2110,null,2111,null,2112,null,2113,null,2114,null,2115,null,2116,null,2117,null,2118,null,2119,null,2120,null,2121,null,2122,null,2123,null,2124,null,2125,null,2126,null,2127,null,2128,null,2129,null,2130,null,2131,null,2132,null,2133,null,2134,null,2135,null,2136,null,2137,null,2138,null,2139,null,2140,null,2141,null,2142,null,2143,null,2144,null,2145,null,2146,null,2147,null,2148,null,2149,null,2150,null,2151,null,2152,null,2153,null,2154,null,2155,null,2156,null,2157,null,2158,null,2159,null,2160,null,2161,null,2162,null,2163,null,2164,null,2165,null,2166,null,2167,null,2168,null,2169,null,2170,null,2171,null,2172,null,2173,null,2174,null,2175,null,2176,null,2177,null,2178,null,2179,null,2180,null,2181,null,2182,null,2183,null,2184,null,2185,null,2186,null,2187,null,2188,null,2189,null,2190,null,2191,null,2192,null,2193,null,2194,null,2195,null,2196,null,2197,null,2198,null,2199,null,2200,null,2201,null,2202,null,2203,null,2204,null,2205,null,2206,null,2207,null,2208,null,2209,null,2210,null,2211,null,2212,null,2213,null,2214,null,2215,null,2216,null,2217,null,2218,null,2219,null,2220,null,2221,null,2222,null,2223,null,2224,null,2225,null,2226,null,2227,null,2228,null,2229,null,2230,null,2231,null,2232,null,2233,null,2234,null,2235,null,2236,null,2237,null,2238,null,2239,null,2240,null,2241,null,2242,null,2243,null,2244,null,2245,null,2246,null,2247,null,2248,null,2249,null,2250,null,2251,null,2252,null,2253,null,2254,null,2255,null,2256,null,2257,null,2258,null,2259,null,2260,null,2261,null,2262,null,2263,null,2264,null,2265,null,2266,null,2267,null,2268,null,2269,null,2270,null,2271,null,2272,null,2273,null,2274,null,2275,null,2276,null,2277,null,2278,null,2279,null,2280,null,2281,null,2282,null,2283,null,2284,null,2285,null,2286,null,2287,null,2288,null,2289,null,2290,null,2291,null,2292,null,2293,null,2294,null,2295,null,2296,null,2297,null,2298,null,2299,null,2300,null,2301,null,2302,null,2303,null,2304,null,2305,null,2306,null,2307,null,2308,null,2309,null,2310,null,2311,null,2312,null,2313,null,2314,null,2315,null,2316,null,2317,null,2318,null,2319,null,2320,null,2321,null,2322,null,2323,null,2324,null,2325,null,2326,null,2327,null,2328,null,2329,null,2330,null,2331,null,2332,null,2333,null,2334,null,2335,null,2336,null,2337,null,2338,null,2339,null,2340,null,2341,null,2342,null,2343,null,2344,null,2345,null,2346,null,2347,null,2348,null,2349,null,2350,null,2351,null,2352,null,2353,null,2354,null,2355,null,2356,null,2357,null,2358,null,2359,null,2360,null,2361,null,2362,null,2363,null,2364,null,2365,null,2366,null,2367,null,2368,null,2369,null,2370,null,2371,null,2372,null,2373,null,2374,null,2375,null,2376,null,2377,null,2378,null,2379,null,2380,null,2381,null,2382,null,2383,null,2384,null,2385,null,2386,null,2387,null,2388,null,2389,null,2390,null,2391,null,2392,null,2393,null,2394,null,2395,null,2396,null,2397,null,2398,null,2399,null,2400,null,2401,null,2402,null,2403,null,2404,null,2405,null,2406,null,2407,null,2408,null,2409,null,2410,null,2411,null,2412,null,2413,null,2414,null,2415,null,2416,null,2417,null,2418,null,2419,null,2420,null,2421,null,2422,null,2423,null,2424,null,2425,null,2426,null,2427,null,2428,null,2429,null,2430,null,2431,null,2432,null,2433,null,2434,null,2435,null,2436,null,2437,null,2438,null,2439,null,2440,null,2441,null,2442,null,2443,null,2444,null,2445,null,2446,null,2447,null,2448,null,2449,null,2450,null,2451,null,2452,null,2453,null,2454,null,2455,null,2456,null,2457,null,2458,null,2459,null,2460,null,2461,null,2462,null,2463,null,2464,null,2465,null,2466,null,2467,null,2468,null,2469,null,2470,null,2471,null,2472,null,2473,null,2474,null,2475,null,2476,null,2477,null,2478,null,2479,null,2480,null,2481,null,2482,null,2483,null,2484,null,2485,null,2486,null,2487,null,2488,null,2489,null,2490,null,2491,null,2492,null,2493,null,2494,null,2495,null,2496,null,2497,null,2498,null,2499,null,2500,null,2501,null,2502,null,2503,null,2504,null,2505,null,2506,null,2507,null,2508,null,2509,null,2510,null,2511,null,2512,null,2513,null,2514,null,2515,null,2516,null,2517,null,2518,null,2519,null,2520,null,2521,null,2522,null,2523,null,2524,null,2525,null,2526,null,2527,null,2528,null,2529,null,2530,null,2531,null,2532,null,2533,null,2534,null,2535,null,2536,null,2537,null,2538,null,2539,null,2540,null,2541,null,2542,null,2543,null,2544,null,2545,null,2546,null,2547,null,2548,null,2549,null,2550,null,2551,null,2552,null,2553,null,2554,null,2555,null,2556,null,2557,null,2558,null,2559,null,2560,null,2561,null,2562,null,2563,null,2564,null,2565,null,2566,null,2567,null,2568,null,2569,null,2570,null,2571,null,2572,null,2573,null,2574,null,2575,null,2576,null,2577,null,2578,null,2579,null,2580,null,2581,null,2582,null,2583,null,2584,null,2585,null,2586,null,2587,null,2588,null,2589,null,2590,null,2591,null,2592,null,2593,null,2594,null,2595,null,2596,null,2597,null,2598,null,2599,null,2600,null,2601,null,2602,null,2603,null,2604,null,2605,null,2606,null,2607,null,2608,null,2609,null,2610,null,2611,null,2612,null,2613,null,2614,null,2615,null,2616,null,2617,null,2618,null,2619,null,2620,null,2621,null,2622,null,2623,null,2624,null,2625,null,2626,null,2627,null,2628,null,2629,null,2630,null,2631,null,2632,null,2633,null,2634,null,2635,null,2636,null,2637,null,2638,null,2639,null,2640,null,2641,null,2642,null,2643,null,2644,null,2645,null,2646,null,2647,null,2648,null,2649,null,2650,null,2651,null,2652,null,2653,null,2654,null,2655,null,2656,null,2657,null,2658,null,2659,null,2660,null,2661,null,2662,null,2663,null,2664,null,2665,null,2666,null,2667,null,2668,null,2669,null,2670,null,2671,null,2672,null,2673,null,2674,null,2675,null,2676,null,2677,null,2678,null,2679,null,2680,null,2681,null,2682,null,2683,null,2684,null,2685,null,2686,null,2687,null,2688,null,2689,null,2690,null,2691,null,2692,null,2693,null,2694,null,2695,null,2696,null,2697,null,2698,null,2699,null,2700,null,2701,null,2702,null,2703,null,2704,null,2705,null,2706,null,2707,null,2708,null,2709,null,2710,null,2711,null,2712,null,2713,null,2714,null,2715,null,2716,null,2717,null,2718,null,2719,null,2720,null,2721,null,2722,null,2723,null,2724,null,2725,null,2726,null,2727,null,2728,null,2729,null,2730,null,2731,null,2732,null,2733,null,2734,null,2735,null,2736,null,2737,null,2738,null,2739,null,2740,null,2741,null,2742,null,2743,null,2744,null,2745,null,2746,null,2747,null,2748,null,2749,null,2750,null,2751,null,2752,null,2753,null,2754,null,2755,null,2756,null,2757,null,2758,null,2759,null,2760,null,2761,null,2762,null,2763,null,2764,null,2765,null,2766,null,2767,null,2768,null,2769,null,2770,null,2771,null,2772,null,2773,null,2774,null,2775,null,2776,null,2777,null,2778,null,2779,null,2780,null,2781,null,2782,null,2783,null,2784,null,2785,null,2786,null,2787,null,2788,null,2789,null,2790,null,2791,null,2792,null,2793,null,2794,null,2795,null,2796,null,2797,null,2798,null,2799,null,2800,null,2801,null,2802,null,2803,null,2804,null,2805,null,2806,null,2807,null,2808,null,2809,null,2810,null,2811,null,2812,null,2813,null,2814,null,2815,null,2816,null,2817,null,2818,null,2819,null,2820,null,2821,null,2822,null,2823,null,2824,null,2825,null,2826,null,2827,null,2828,null,2829,null,2830,null,2831,null,2832,null,2833,null,2834,null,2835,null,2836,null,2837,null,2838,null,2839,null,2840,null,2841,null,2842,null,2843,null,2844,null,2845,null,2846,null,2847,null,2848,null,2849,null,2850,null,2851,null,2852,null,2853,null,2854,null,2855,null,2856,null,2857,null,2858,null,2859,null,2860,null,2861,null,2862,null,2863,null,2864,null,2865,null,2866,null,2867,null,2868,null,2869,null,2870,null,2871,null,2872,null,2873,null,2874,null,2875,null,2876,null,2877,null,2878,null,2879,null,2880,null,2881,null,2882,null,2883,null,2884,null,2885,null,2886,null,2887,null,2888,null,2889,null,2890,null,2891,null,2892,null,2893,null,2894,null,2895,null,2896,null,2897,null,2898,null,2899,null,2900,null,2901,null,2902,null,2903,null,2904,null,2905,null,2906,null,2907,null,2908,null,2909,null,2910,null,2911,null,2912,null,2913,null,2914,null,2915,null,2916,null,2917,null,2918,null,2919,null,2920,null,2921,null,2922,null,2923,null,2924,null,2925,null,2926,null,2927,null,2928,null,2929,null,2930,null,2931,null,2932,null,2933,null,2934,null,2935,null,2936,null,2937,null,2938,null,2939,null,2940,null,2941,null,2942,null,2943,null,2944,null,2945,null,2946,null,2947,null,2948,null,2949,null,2950,null,2951,null,2952,null,2953,null,2954,null,2955,null,2956,null,2957,null,2958,null,2959,null,2960,null,2961,null,2962,null,2963,null,2964,null,2965,null,2966,null,2967,null,2968,null,2969,null,2970,null,2971,null,2972,null,2973,null,2974,null,2975,null,2976,null,2977,null,2978,null,2979,null,2980,null,2981,null,2982,null,2983,null,2984,null,2985,null,2986,null,2987,null,2988,null,2989,null,2990,null,2991,null,2992,null,2993,null,2994,null,2995,null,2996,null,2997,null,2998,null,2999,null,3000,null,3001,null,3002,null,3003,null,3004,null,3005,null,3006,null,3007,null,3008,null,3009,null,3010,null,3011,null,3012,null,3013,null,3014,null,3015,null,3016,null,3017,null,3018,null,3019,null,3020,null,3021,null,3022,null,3023,null,3024,null,3025,null,3026,null,3027,null,3028,null,3029,null,3030,null,3031,null,3032,null,3033,null,3034,null,3035,null,3036,null,3037,null,3038,null,3039,null,3040,null,3041,null,3042,null,3043,null,3044,null,3045,null,3046,null,3047,null,3048,null,3049,null,3050,null,3051,null,3052,null,3053,null,3054,null,3055,null,3056,null,3057,null,3058,null,3059,null,3060,null,3061,null,3062,null,3063,null,3064,null,3065,null,3066,null,3067,null,3068,null,3069,null,3070,null,3071,null,3072,null,3073,null,3074,null,3075,null,3076,null,3077,null,3078,null,3079,null,3080,null,3081,null,3082,null,3083,null,3084,null,3085,null,3086,null,3087,null,3088,null,3089,null,3090,null,3091,null,3092,null,3093,null,3094,null,3095,null,3096,null,3097,null,3098,null,3099,null,3100,null,3101,null,3102,null,3103,null,3104,null,3105,null,3106,null,3107,null,3108,null,3109,null,3110,null,3111,null,3112,null,3113,null,3114,null,3115,null,3116,null,3117,null,3118,null,3119,null,3120,null,3121,null,3122,null,3123,null,3124,null,3125,null,3126,null,3127,null,3128,null,3129,null,3130,null,3131,null,3132,null,3133,null,3134,null,3135,null,3136,null,3137,null,3138,null,3139,null,3140,null,3141,null,3142,null,3143,null,3144,null,3145,null,3146,null,3147,null,3148,null,3149,null,3150,null,3151,null,3152,null,3153,null,3154,null,3155,null,3156,null,3157,null,3158,null,3159,null,3160,null,3161,null,3162,null,3163,null,3164,null,3165,null,3166,null,3167,null,3168,null,3169,null,3170,null,3171,null,3172,null,3173,null,3174,null,3175,null,3176,null,3177,null,3178,null,3179,null,3180,null,3181,null,3182,null,3183,null,3184,null,3185,null,3186,null,3187,null,3188,null,3189,null,3190,null,3191,null,3192,null,3193,null,3194,null,3195,null,3196,null,3197,null,3198,null,3199,null,3200,null,3201,null,3202,null,3203,null,3204,null,3205,null,3206,null,3207,null,3208,null,3209,null,3210,null,3211,null,3212,null,3213,null,3214,null,3215,null,3216,null,3217,null,3218,null,3219,null,3220,null,3221,null,3222,null,3223,null,3224,null,3225,null,3226,null,3227,null,3228,null,3229,null,3230,null,3231,null,3232,null,3233,null,3234,null,3235,null,3236,null,3237,null,3238,null,3239,null,3240,null,3241,null,3242,null,3243,null,3244,null,3245,null,3246,null,3247,null,3248,null,3249,null,3250,null,3251,null,3252,null,3253,null,3254,null,3255,null,3256,null,3257,null,3258,null,3259,null,3260,null,3261,null,3262,null,3263,null,3264,null,3265,null,3266,null,3267,null,3268,null,3269,null,3270,null,3271,null,3272,null,3273,null,3274,null,3275,null,3276,null,3277,null,3278,null,3279,null,3280,null,3281,null,3282,null,3283,null,3284,null,3285,null,3286,null,3287,null,3288,null,3289,null,3290,null,3291,null,3292,null,3293,null,3294,null,3295,null,3296,null,3297,null,3298,null,3299,null,3300,null,3301,null,3302,null,3303,null,3304,null,3305,null,3306,null,3307,null,3308,null,3309,null,3310,null,3311,null,3312,null,3313,null,3314,null,3315,null,3316,null,3317,null,3318,null,3319,null,3320,null,3321,null,3322,null,3323,null,3324,null,3325,null,3326,null,3327,null,3328,null,3329,null,3330,null,3331,null,3332,null,3333,null,3334,null,3335,null,3336,null,3337,null,3338,null,3339,null,3340,null,3341,null,3342,null,3343,null,3344,null,3345,null,3346,null,3347,null,3348,null,3349,null,3350,null,3351,null,3352,null,3353,null,3354,null,3355,null,3356,null,3357,null,3358,null,3359,null,3360,null,3361,null,3362,null,3363,null,3364,null,3365,null,3366,null,3367,null,3368,null,3369,null,3370,null,3371,null,3372,null,3373,null,3374,null,3375,null,3376,null,3377,null,3378,null,3379,null,3380,null,3381,null,3382,null,3383,null,3384,null,3385,null,3386,null,3387,null,3388,null,3389,null,3390,null,3391,null,3392,null,3393,null,3394,null,3395,null,3396,null,3397,null,3398,null,3399,null,3400,null,3401,null,3402,null,3403,null,3404,null,3405,null,3406,null,3407,null,3408,null,3409,null,3410,null,3411,null,3412,null,3413,null,3414,null,3415,null,3416,null,3417,null,3418,null,3419,null,3420,null,3421,null,3422,null,3423,null,3424,null,3425,null,3426,null,3427,null,3428,null,3429,null,3430,null,3431,null,3432,null,3433,null,3434,null,3435,null,3436,null,3437,null,3438,null,3439,null,3440,null,3441,null,3442,null,3443,null,3444,null,3445,null,3446,null,3447,null,3448,null,3449,null,3450,null,3451,null,3452,null,3453,null,3454,null,3455,null,3456,null,3457,null,3458,null,3459,null,3460,null,3461,null,3462,null,3463,null,3464,null,3465,null,3466,null,3467,null,3468,null,3469,null,3470,null,3471,null,3472,null,3473,null,3474,null,3475,null,3476,null,3477,null,3478,null,3479,null,3480,null,3481,null,3482,null,3483,null,3484,null,3485,null,3486,null,3487,null,3488,null,3489,null,3490,null,3491,null,3492,null,3493,null,3494,null,3495,null,3496,null,3497,null,3498,null,3499,null,3500,null,3501,null,3502,null,3503,null,3504,null,3505,null,3506,null,3507,null,3508,null,3509,null,3510,null,3511,null,3512,null,3513,null,3514,null,3515,null,3516,null,3517,null,3518,null,3519,null,3520,null,3521,null,3522,null,3523,null,3524,null,3525,null,3526,null,3527,null,3528,null,3529,null,3530,null,3531,null,3532,null,3533,null,3534,null,3535,null,3536,null,3537,null,3538,null,3539,null,3540,null,3541,null,3542,null,3543,null,3544,null,3545,null,3546,null,3547,null,3548,null,3549,null,3550,null,3551,null,3552,null,3553,null,3554,null,3555,null,3556,null,3557,null,3558,null,3559,null,3560,null,3561,null,3562,null,3563,null,3564,null,3565,null,3566,null,3567,null,3568,null,3569,null,3570,null,3571,null,3572,null,3573,null,3574,null,3575,null,3576,null,3577,null,3578,null,3579,null,3580,null,3581,null,3582,null,3583,null,3584,null,3585,null,3586,null,3587,null,3588,null,3589,null,3590,null,3591,null,3592,null,3593,null,3594,null,3595,null,3596,null,3597,null,3598,null,3599,null,3600,null,3601,null,3602,null,3603,null,3604,null,3605,null,3606,null,3607,null,3608,null,3609,null,3610,null,3611,null,3612,null,3613,null,3614,null,3615,null,3616,null,3617,null,3618,null,3619,null,3620,null,3621,null,3622,null,3623,null,3624,null,3625,null,3626,null,3627,null,3628,null,3629,null,3630,null,3631,null,3632,null,3633,null,3634,null,3635,null,3636,null,3637,null,3638,null,3639,null,3640,null,3641,null,3642,null,3643,null,3644,null,3645,null,3646,null,3647,null,3648,null,3649,null,3650,null,3651,null,3652,null,3653,null,3654,null,3655,null,3656,null,3657,null,3658,null,3659,null,3660,null,3661,null,3662,null,3663,null,3664,null,3665,null,3666,null,3667,null,3668,null,3669,null,3670,null,3671,null,3672,null,3673,null,3674,null,3675,null,3676,null,3677,null,3678,null,3679,null,3680,null,3681,null,3682,null,3683,null,3684,null,3685,null,3686,null,3687,null,3688,null,3689,null,3690,null,3691,null,3692,null,3693,null,3694,null,3695,null,3696,null,3697,null,3698,null,3699,null,3700,null,3701,null,3702,null,3703,null,3704,null,3705,null,3706,null,3707,null,3708,null,3709,null,3710,null,3711,null,3712,null,3713,null,3714,null,3715,null,3716,null,3717,null,3718,null,3719,null,3720,null,3721,null,3722,null,3723,null,3724,null,3725,null,3726,null,3727,null,3728,null,3729,null,3730,null,3731,null,3732,null,3733,null,3734,null,3735,null,3736,null,3737,null,3738,null,3739,null,3740,null,3741,null,3742,null,3743,null,3744,null,3745,null,3746,null,3747,null,3748,null,3749,null,3750,null,3751,null,3752,null,3753,null,3754,null,3755,null,3756,null,3757,null,3758,null,3759,null,3760,null,3761,null,3762,null,3763,null,3764,null,3765,null,3766,null,3767,null,3768,null,3769,null,3770,null,3771,null,3772,null,3773,null,3774,null,3775,null,3776,null,3777,null,3778,null,3779,null,3780,null,3781,null,3782,null,3783,null,3784,null,3785,null,3786,null,3787,null,3788,null,3789,null,3790,null,3791,null,3792,null,3793,null,3794,null,3795,null,3796,null,3797,null,3798,null,3799,null,3800,null,3801,null,3802,null,3803,null,3804,null,3805,null,3806,null,3807,null,3808,null,3809,null,3810,null,3811,null,3812,null,3813,null,3814,null,3815,null,3816,null,3817,null,3818,null,3819,null,3820,null,3821,null,3822,null,3823,null,3824,null,3825,null,3826,null,3827,null,3828,null,3829,null,3830,null,3831,null,3832,null,3833,null,3834,null,3835,null,3836,null,3837,null,3838,null,3839,null,3840,null,3841,null,3842,null,3843,null,3844,null,3845,null,3846,null,3847,null,3848,null,3849,null,3850,null,3851,null,3852,null,3853,null,3854,null,3855,null,3856,null,3857,null,3858,null,3859,null,3860,null,3861,null,3862,null,3863,null,3864,null,3865,null,3866,null,3867,null,3868,null,3869,null,3870,null,3871,null,3872,null,3873,null,3874,null,3875,null,3876,null,3877,null,3878,null,3879,null,3880,null,3881,null,3882,null,3883,null,3884,null,3885,null,3886,null,3887,null,3888,null,3889,null,3890,null,3891,null,3892,null,3893,null,3894,null,3895,null,3896,null,3897,null,3898,null,3899,null,3900,null,3901,null,3902,null,3903,null,3904,null,3905,null,3906,null,3907,null,3908,null,3909,null,3910,null,3911,null,3912,null,3913,null,3914,null,3915,null,3916,null,3917,null,3918,null,3919,null,3920,null,3921,null,3922,null,3923,null,3924,null,3925,null,3926,null,3927,null,3928,null,3929,null,3930,null,3931,null,3932,null,3933,null,3934,null,3935,null,3936,null,3937,null,3938,null,3939,null,3940,null,3941,null,3942,null,3943,null,3944,null,3945,null,3946,null,3947,null,3948,null,3949,null,3950,null,3951,null,3952,null,3953,null,3954,null,3955,null,3956,null,3957,null,3958,null,3959,null,3960,null,3961,null,3962,null,3963,null,3964,null,3965,null,3966,null,3967,null,3968,null,3969,null,3970,null,3971,null,3972,null,3973,null,3974,null,3975,null,3976,null,3977,null,3978,null,3979,null,3980,null,3981,null,3982,null,3983,null,3984,null,3985,null,3986,null,3987,null,3988,null,3989,null,3990,null,3991,null,3992,null,3993,null,3994,null,3995,null,3996,null,3997,null,3998,null,3999,null,4000,null,4001,null,4002,null,4003,null,4004,null,4005,null,4006,null,4007,null,4008,null,4009,null,4010,null,4011,null,4012,null,4013,null,4014,null,4015,null,4016,null,4017,null,4018,null,4019,null,4020,null,4021,null,4022,null,4023,null,4024,null,4025,null,4026,null,4027,null,4028,null,4029,null,4030,null,4031,null,4032,null,4033,null,4034,null,4035,null,4036,null,4037,null,4038,null,4039,null,4040,null,4041,null,4042,null,4043,null,4044,null,4045,null,4046,null,4047,null,4048,null,4049,null,4050,null,4051,null,4052,null,4053,null,4054,null,4055,null,4056,null,4057,null,4058,null,4059,null,4060,null,4061,null,4062,null,4063,null,4064,null,4065,null,4066,null,4067,null,4068,null,4069,null,4070,null,4071,null,4072,null,4073,null,4074,null,4075,null,4076,null,4077,null,4078,null,4079,null,4080,null,4081,null,4082,null,4083,null,4084,null,4085,null,4086,null,4087,null,4088,null,4089,null,4090,null,4091,null,4092,null,4093,null,4094,null,4095,null,4096,null,4097,null,4098,null,4099,null,4100,null,4101,null,4102,null,4103,null,4104,null,4105,null,4106,null,4107,null,4108,null,4109,null,4110,null,4111,null,4112,null,4113,null,4114,null,4115,null,4116,null,4117,null,4118,null,4119,null,4120,null,4121,null,4122,null,4123,null,4124,null,4125,null,4126,null,4127,null,4128,null,4129,null,4130,null,4131,null,4132,null,4133,null,4134,null,4135,null,4136,null,4137,null,4138,null,4139,null,4140,null,4141,null,4142,null,4143,null,4144,null,4145,null,4146,null,4147,null,4148,null,4149,null,4150,null,4151,null,4152,null,4153,null,4154,null,4155,null,4156,null,4157,null,4158,null,4159,null,4160,null,4161,null,4162,null,4163,null,4164,null,4165,null,4166,null,4167,null,4168,null,4169,null,4170,null,4171,null,4172,null,4173,null,4174,null,4175,null,4176,null,4177,null,4178,null,4179,null,4180,null,4181,null,4182,null,4183,null,4184,null,4185,null,4186,null,4187,null,4188,null,4189,null,4190,null,4191,null,4192,null,4193,null,4194,null,4195,null,4196,null,4197,null,4198,null,4199,null,4200,null,4201,null,4202,null,4203,null,4204,null,4205,null,4206,null,4207,null,4208,null,4209,null,4210,null,4211,null,4212,null,4213,null,4214,null,4215,null,4216,null,4217,null,4218,null,4219,null,4220,null,4221,null,4222,null,4223,null,4224,null,4225,null,4226,null,4227,null,4228,null,4229,null,4230,null,4231,null,4232,null,4233,null,4234,null,4235,null,4236,null,4237,null,4238,null,4239,null,4240,null,4241,null,4242,null,4243,null,4244,null,4245,null,4246,null,4247,null,4248,null,4249,null,4250,null,4251,null,4252,null,4253,null,4254,null,4255,null,4256,null,4257,null,4258,null,4259,null,4260,null,4261,null,4262,null,4263,null,4264,null,4265,null,4266,null,4267,null,4268,null,4269,null,4270,null,4271,null,4272,null,4273,null,4274,null,4275,null,4276,null,4277,null,4278,null,4279,null,4280,null,4281,null,4282,null,4283,null,4284,null,4285,null,4286,null,4287,null,4288,null,4289,null,4290,null,4291,null,4292,null,4293,null,4294,null,4295,null,4296,null,4297,null,4298,null,4299,null,4300,null,4301,null,4302,null,4303,null,4304,null,4305,null,4306,null,4307,null,4308,null,4309,null,4310,null,4311,null,4312,null,4313,null,4314,null,4315,null,4316,null,4317,null,4318,null,4319,null,4320,null,4321,null,4322,null,4323,null,4324,null,4325,null,4326,null,4327,null,4328,null,4329,null,4330,null,4331,null,4332,null,4333,null,4334,null,4335,null,4336,null,4337,null,4338,null,4339,null,4340,null,4341,null,4342,null,4343,null,4344,null,4345,null,4346,null,4347,null,4348,null,4349,null,4350,null,4351,null,4352,null,4353,null,4354,null,4355,null,4356,null,4357,null,4358,null,4359,null,4360,null,4361,null,4362,null,4363,null,4364,null,4365,null,4366,null,4367,null,4368,null,4369,null,4370,null,4371,null,4372,null,4373,null,4374,null,4375,null,4376,null,4377,null,4378,null,4379,null,4380,null,4381,null,4382,null,4383,null,4384,null,4385,null,4386,null,4387,null,4388,null,4389,null,4390,null,4391,null,4392,null,4393,null,4394,null,4395,null,4396,null,4397,null,4398,null,4399,null,4400,null,4401,null,4402,null,4403,null,4404,null,4405,null,4406,null,4407,null,4408,null,4409,null,4410,null,4411,null,4412,null,4413,null,4414,null,4415,null,4416,null,4417,null,4418,null,4419,null,4420,null,4421,null,4422,null,4423,null,4424,null,4425,null,4426,null,4427,null,4428,null,4429,null,4430,null,4431,null,4432,null,4433,null,4434,null,4435,null,4436,null,4437,null,4438,null,4439,null,4440,null,4441,null,4442,null,4443,null,4444,null,4445,null,4446,null,4447,null,4448,null,4449,null,4450,null,4451,null,4452,null,4453,null,4454,null,4455,null,4456,null,4457,null,4458,null,4459,null,4460,null,4461,null,4462,null,4463,null,4464,null,4465,null,4466,null,4467,null,4468,null,4469,null,4470,null,4471,null,4472,null,4473,null,4474,null,4475,null,4476,null,4477,null,4478,null,4479,null,4480,null,4481,null,4482,null,4483,null,4484,null,4485,null,4486,null,4487,null,4488,null,4489,null,4490,null,4491,null,4492,null,4493,null,4494,null,4495,null,4496,null,4497,null,4498,null,4499,null,4500,null,4501,null,4502,null,4503,null,4504,null,4505,null,4506,null,4507,null,4508,null,4509,null,4510,null,4511,null,4512,null,4513,null,4514,null,4515,null,4516,null,4517,null,4518,null,4519,null,4520,null,4521,null,4522,null,4523,null,4524,null,4525,null,4526,null,4527,null,4528,null,4529,null,4530,null,4531,null,4532,null,4533,null,4534,null,4535,null,4536,null,4537,null,4538,null,4539,null,4540,null,4541,null,4542,null,4543,null,4544,null,4545,null,4546,null,4547,null,4548,null,4549,null,4550,null,4551,null,4552,null,4553,null,4554,null,4555,null,4556,null,4557,null,4558,null,4559,null,4560,null,4561,null,4562,null,4563,null,4564,null,4565,null,4566,null,4567,null,4568,null,4569,null,4570,null,4571,null,4572,null,4573,null,4574,null,4575,null,4576,null,4577,null,4578,null,4579,null,4580,null,4581,null,4582,null,4583,null,4584,null,4585,null,4586,null,4587,null,4588,null,4589,null,4590,null,4591,null,4592,null,4593,null,4594,null,4595,null,4596,null,4597,null,4598,null,4599,null,4600,null,4601,null,4602,null,4603,null,4604,null,4605,null,4606,null,4607,null,4608,null,4609,null,4610,null,4611,null,4612,null,4613,null,4614,null,4615,null,4616,null,4617,null,4618,null,4619,null,4620,null,4621,null,4622,null,4623,null,4624,null,4625,null,4626,null,4627,null,4628,null,4629,null,4630,null,4631,null,4632,null,4633,null,4634,null,4635,null,4636,null,4637,null,4638,null,4639,null,4640,null,4641,null,4642,null,4643,null,4644,null,4645,null,4646,null,4647,null,4648,null,4649,null,4650,null,4651,null,4652,null,4653,null,4654,null,4655,null,4656,null,4657,null,4658,null,4659,null,4660,null,4661,null,4662,null,4663,null,4664,null,4665,null,4666,null,4667,null,4668,null,4669,null,4670,null,4671,null,4672,null,4673,null,4674,null,4675,null,4676,null,4677,null,4678,null,4679,null,4680,null,4681,null,4682,null,4683,null,4684,null,4685,null,4686,null,4687,null,4688,null,4689,null,4690,null,4691,null,4692,null,4693,null,4694,null,4695,null,4696,null,4697,null,4698,null,4699,null,4700,null,4701,null,4702,null,4703,null,4704,null,4705,null,4706,null,4707,null,4708,null,4709,null,4710,null,4711,null,4712,null,4713,null,4714,null,4715,null,4716,null,4717,null,4718,null,4719,null,4720,null,4721,null,4722,null,4723,null,4724,null,4725,null,4726,null,4727,null,4728,null,4729,null,4730,null,4731,null,4732,null,4733,null,4734,null,4735,null,4736,null,4737,null,4738,null,4739,null,4740,null,4741,null,4742,null,4743,null,4744,null,4745,null,4746,null,4747,null,4748,null,4749,null,4750,null,4751,null,4752,null,4753,null,4754,null,4755,null,4756,null,4757,null,4758,null,4759,null,4760,null,4761,null,4762,null,4763,null,4764,null,4765,null,4766,null,4767,null,4768,null,4769,null,4770,null,4771,null,4772,null,4773,null,4774,null,4775,null,4776,null,4777,null,4778,null,4779,null,4780,null,4781,null,4782,null,4783,null,4784,null,4785,null,4786,null,4787,null,4788,null,4789,null,4790,null,4791,null,4792,null,4793,null,4794,null,4795,null,4796,null,4797,null,4798,null,4799,null,4800,null,4801,null,4802,null,4803,null,4804,null,4805,null,4806,null,4807,null,4808,null,4809,null,4810,null,4811,null,4812,null,4813,null,4814,null,4815,null,4816,null,4817,null,4818,null,4819,null,4820,null,4821,null,4822,null,4823,null,4824,null,4825,null,4826,null,4827,null,4828,null,4829,null,4830,null,4831,null,4832,null,4833,null,4834,null,4835,null,4836,null,4837,null,4838,null,4839,null,4840,null,4841,null,4842,null,4843,null,4844,null,4845,null,4846,null,4847,null,4848,null,4849,null,4850,null,4851,null,4852,null,4853,null,4854,null,4855,null,4856,null,4857,null,4858,null,4859,null,4860,null,4861,null,4862,null,4863,null,4864,null,4865,null,4866,null,4867,null,4868,null,4869,null,4870,null,4871,null,4872,null,4873,null,4874,null,4875,null,4876,null,4877,null,4878,null,4879,null,4880,null,4881,null,4882,null,4883,null,4884,null,4885,null,4886,null,4887,null,4888,null,4889,null,4890,null,4891,null,4892,null,4893,null,4894,null,4895,null,4896,null,4897,null,4898,null,4899,null,4900,null,4901,null,4902,null,4903,null,4904,null,4905,null,4906,null,4907,null,4908,null,4909,null,4910,null,4911,null,4912,null,4913,null,4914,null,4915,null,4916,null,4917,null,4918,null,4919,null,4920,null,4921,null,4922,null,4923,null,4924,null,4925,null,4926,null,4927,null,4928,null,4929,null,4930,null,4931,null,4932,null,4933,null,4934,null,4935,null,4936,null,4937,null,4938,null,4939,null,4940,null,4941,null,4942,null,4943,null,4944,null,4945,null,4946,null,4947,null,4948,null,4949,null,4950,null,4951,null,4952,null,4953,null,4954,null,4955,null,4956,null,4957,null,4958,null,4959,null,4960,null,4961,null,4962,null,4963,null,4964,null,4965,null,4966,null,4967,null,4968,null,4969,null,4970,null,4971,null,4972,null,4973,null,4974,null,4975,null,4976,null,4977,null,4978,null,4979,null,4980,null,4981,null,4982,null,4983,null,4984,null,4985,null,4986,null,4987,null,4988,null,4989,null,4990,null,4991,null,4992,null,4993,null,4994,null,4995,null,4996,null,4997,null,4998,null,4999,null,5000,null,5001,null,5002,null,5003,null,5004,null,5005,null,5006,null,5007,null,5008,null,5009,null,5010,null,5011,null,5012,null,5013,null,5014,null,5015,null,5016,null,5017,null,5018,null,5019,null,5020,null,5021,null,5022,null,5023,null,5024,null,5025,null,5026,null,5027,null,5028,null,5029,null,5030,null,5031,null,5032,null,5033,null,5034,null,5035,null,5036,null,5037,null,5038,null,5039,null,5040,null,5041,null,5042,null,5043,null,5044,null,5045,null,5046,null,5047,null,5048,null,5049,null,5050,null,5051,null,5052,null,5053,null,5054,null,5055,null,5056,null,5057,null,5058,null,5059,null,5060,null,5061,null,5062,null,5063,null,5064,null,5065,null,5066,null,5067,null,5068,null,5069,null,5070,null,5071,null,5072,null,5073,null,5074,null,5075,null,5076,null,5077,null,5078,null,5079,null,5080,null,5081,null,5082,null,5083,null,5084,null,5085,null,5086,null,5087,null,5088,null,5089,null,5090,null,5091,null,5092,null,5093,null,5094,null,5095,null,5096,null,5097,null,5098,null,5099,null,5100,null,5101,null,5102,null,5103,null,5104,null,5105,null,5106,null,5107,null,5108,null,5109,null,5110,null,5111,null,5112,null,5113,null,5114,null,5115,null,5116,null,5117,null,5118,null,5119,null,5120,null,5121,null,5122,null,5123,null,5124,null,5125,null,5126,null,5127,null,5128,null,5129,null,5130,null,5131,null,5132,null,5133,null,5134,null,5135,null,5136,null,5137,null,5138,null,5139,null,5140,null,5141,null,5142,null,5143,null,5144,null,5145,null,5146,null,5147,null,5148,null,5149,null,5150,null,5151,null,5152,null,5153,null,5154,null,5155,null,5156,null,5157,null,5158,null,5159,null,5160,null,5161,null,5162,null,5163,null,5164,null,5165,null,5166,null,5167,null,5168,null,5169,null,5170,null,5171,null,5172,null,5173,null,5174,null,5175,null,5176,null,5177,null,5178,null,5179,null,5180,null,5181,null,5182,null,5183,null,5184,null,5185,null,5186,null,5187,null,5188,null,5189,null,5190,null,5191,null,5192,null,5193,null,5194,null,5195,null,5196,null,5197,null,5198,null,5199,null,5200,null,5201,null,5202,null,5203,null,5204,null,5205,null,5206,null,5207,null,5208,null,5209,null,5210,null,5211,null,5212,null,5213,null,5214,null,5215,null,5216,null,5217,null,5218,null,5219,null,5220,null,5221,null,5222,null,5223,null,5224,null,5225,null,5226,null,5227,null,5228,null,5229,null,5230,null,5231,null,5232,null,5233,null,5234,null,5235,null,5236,null,5237,null,5238,null,5239,null,5240,null,5241,null,5242,null,5243,null,5244,null,5245,null,5246,null,5247,null,5248,null,5249,null,5250,null,5251,null,5252,null,5253,null,5254,null,5255,null,5256,null,5257,null,5258,null,5259,null,5260,null,5261,null,5262,null,5263,null,5264,null,5265,null,5266,null,5267,null,5268,null,5269,null,5270,null,5271,null,5272,null,5273,null,5274,null,5275,null,5276,null,5277,null,5278,null,5279,null,5280,null,5281,null,5282,null,5283,null,5284,null,5285,null,5286,null,5287,null,5288,null,5289,null,5290,null,5291,null,5292,null,5293,null,5294,null,5295,null,5296,null,5297,null,5298,null,5299,null,5300,null,5301,null,5302,null,5303,null,5304,null,5305,null,5306,null,5307,null,5308,null,5309,null,5310,null,5311,null,5312,null,5313,null,5314,null,5315,null,5316,null,5317,null,5318,null,5319,null,5320,null,5321,null,5322,null,5323,null,5324,null,5325,null,5326,null,5327,null,5328,null,5329,null,5330,null,5331,null,5332,null,5333,null,5334,null,5335,null,5336,null,5337,null,5338,null,5339,null,5340,null,5341,null,5342,null,5343,null,5344,null,5345,null,5346,null,5347,null,5348,null,5349,null,5350,null,5351,null,5352,null,5353,null,5354,null,5355,null,5356,null,5357,null,5358,null,5359,null,5360,null,5361,null,5362,null,5363,null,5364,null,5365,null,5366,null,5367,null,5368,null,5369,null,5370,null,5371,null,5372,null,5373,null,5374,null,5375,null,5376,null,5377,null,5378,null,5379,null,5380,null,5381,null,5382,null,5383,null,5384,null,5385,null,5386,null,5387,null,5388,null,5389,null,5390,null,5391,null,5392,null,5393,null,5394,null,5395,null,5396,null,5397,null,5398,null,5399,null,5400,null,5401,null,5402,null,5403,null,5404,null,5405,null,5406,null,5407,null,5408,null,5409,null,5410,null,5411,null,5412,null,5413,null,5414,null,5415,null,5416,null,5417,null,5418,null,5419,null,5420,null,5421,null,5422,null,5423,null,5424,null,5425,null,5426,null,5427,null,5428,null,5429,null,5430,null,5431,null,5432,null,5433,null,5434,null,5435,null,5436,null,5437,null,5438,null,5439,null,5440,null,5441,null,5442,null,5443,null,5444,null,5445,null,5446,null,5447,null,5448,null,5449,null,5450,null,5451,null,5452,null,5453,null,5454,null,5455,null,5456,null,5457,null,5458,null,5459,null,5460,null,5461,null,5462,null,5463,null,5464,null,5465,null,5466,null,5467,null,5468,null,5469,null,5470,null,5471,null,5472,null,5473,null,5474,null,5475,null,5476,null,5477,null,5478,null,5479,null,5480,null,5481,null,5482,null,5483,null,5484,null,5485,null,5486,null,5487,null,5488,null,5489,null,5490,null,5491,null,5492,null,5493,null,5494,null,5495,null,5496,null,5497,null,5498,null,5499,null,5500,null,5501,null,5502,null,5503,null,5504,null,5505,null,5506,null,5507,null,5508,null,5509,null,5510,null,5511,null,5512,null,5513,null,5514,null,5515,null,5516,null,5517,null,5518,null,5519,null,5520,null,5521,null,5522,null,5523,null,5524,null,5525,null,5526,null,5527,null,5528,null,5529,null,5530,null,5531,null,5532,null,5533,null,5534,null,5535,null,5536,null,5537,null,5538,null,5539,null,5540,null,5541,null,5542,null,5543,null,5544,null,5545,null,5546,null,5547,null,5548,null,5549,null,5550,null,5551,null,5552,null,5553,null,5554,null,5555,null,5556,null,5557,null,5558,null,5559,null,5560,null,5561,null,5562,null,5563,null,5564,null,5565,null,5566,null,5567,null,5568,null,5569,null,5570,null,5571,null,5572,null,5573,null,5574,null,5575,null,5576,null,5577,null,5578,null,5579,null,5580,null,5581,null,5582,null,5583,null,5584,null,5585,null,5586,null,5587,null,5588,null,5589,null,5590,null,5591,null,5592,null,5593,null,5594,null,5595,null,5596,null,5597,null,5598,null,5599,null,5600,null,5601,null,5602,null,5603,null,5604,null,5605,null,5606,null,5607,null,5608,null,5609,null,5610,null,5611,null,5612,null,5613,null,5614,null,5615,null,5616,null,5617,null,5618,null,5619,null,5620,null,5621,null,5622,null,5623,null,5624,null,5625,null,5626,null,5627,null,5628,null,5629,null,5630,null,5631,null,5632,null,5633,null,5634,null,5635,null,5636,null,5637,null,5638,null,5639,null,5640,null,5641,null,5642,null,5643,null,5644,null,5645,null,5646,null,5647,null,5648,null,5649,null,5650,null,5651,null,5652,null,5653,null,5654,null,5655,null,5656,null,5657,null,5658,null,5659,null,5660,null,5661,null,5662,null,5663,null,5664,null,5665,null,5666,null,5667,null,5668,null,5669,null,5670,null,5671,null,5672,null,5673,null,5674,null,5675,null,5676,null,5677,null,5678,null,5679,null,5680,null,5681,null,5682,null,5683,null,5684,null,5685,null,5686,null,5687,null,5688,null,5689,null,5690,null,5691,null,5692,null,5693,null,5694,null,5695,null,5696,null,5697,null,5698,null,5699,null,5700,null,5701,null,5702,null,5703,null,5704,null,5705,null,5706,null,5707,null,5708,null,5709,null,5710,null,5711,null,5712,null,5713,null,5714,null,5715,null,5716,null,5717,null,5718,null,5719,null,5720,null,5721,null,5722,null,5723,null,5724,null,5725,null,5726,null,5727,null,5728,null,5729,null,5730,null,5731,null,5732,null,5733,null,5734,null,5735,null,5736,null,5737,null,5738,null,5739,null,5740,null,5741,null,5742,null,5743,null,5744,null,5745,null,5746,null,5747,null,5748,null,5749,null,5750,null,5751,null,5752,null,5753,null,5754,null,5755,null,5756,null,5757,null,5758,null,5759,null,5760,null,5761,null,5762,null,5763,null,5764,null,5765,null,5766,null,5767,null,5768,null,5769,null,5770,null,5771,null,5772,null,5773,null,5774,null,5775,null,5776,null,5777,null,5778,null,5779,null,5780,null,5781,null,5782,null,5783,null,5784,null,5785,null,5786,null,5787,null,5788,null,5789,null,5790,null,5791,null,5792,null,5793,null,5794,null,5795,null,5796,null,5797,null,5798,null,5799,null,5800,null,5801,null,5802,null,5803,null,5804,null,5805,null,5806,null,5807,null,5808,null,5809,null,5810,null,5811,null,5812,null,5813,null,5814,null,5815,null,5816,null,5817,null,5818,null,5819,null,5820,null,5821,null,5822,null,5823,null,5824,null,5825,null,5826,null,5827,null,5828,null,5829,null,5830,null,5831,null,5832,null,5833,null,5834,null,5835,null,5836,null,5837,null,5838,null,5839,null,5840,null,5841,null,5842,null,5843,null,5844,null,5845,null,5846,null,5847,null,5848,null,5849,null,5850,null,5851,null,5852,null,5853,null,5854,null,5855,null,5856,null,5857,null,5858,null,5859,null,5860,null,5861,null,5862,null,5863,null,5864,null,5865,null,5866,null,5867,null,5868,null,5869,null,5870,null,5871,null,5872,null,5873,null,5874,null,5875,null,5876,null,5877,null,5878,null,5879,null,5880,null,5881,null,5882,null,5883,null,5884,null,5885,null,5886,null,5887,null,5888,null,5889,null,5890,null,5891,null,5892,null,5893,null,5894,null,5895,null,5896,null,5897,null,5898,null,5899,null,5900,null,5901,null,5902,null,5903,null,5904,null,5905,null,5906,null,5907,null,5908,null,5909,null,5910,null,5911,null,5912,null,5913,null,5914,null,5915,null,5916,null,5917,null,5918,null,5919,null,5920,null,5921,null,5922,null,5923,null,5924,null,5925,null,5926,null,5927,null,5928,null,5929,null,5930,null,5931,null,5932,null,5933,null,5934,null,5935,null,5936,null,5937,null,5938,null,5939,null,5940,null,5941,null,5942,null,5943,null,5944,null,5945,null,5946,null,5947,null,5948,null,5949,null,5950,null,5951,null,5952,null,5953,null,5954,null,5955,null,5956,null,5957,null,5958,null,5959,null,5960,null,5961,null,5962,null,5963,null,5964,null,5965,null,5966,null,5967,null,5968,null,5969,null,5970,null,5971,null,5972,null,5973,null,5974,null,5975,null,5976,null,5977,null,5978,null,5979,null,5980,null,5981,null,5982,null,5983,null,5984,null,5985,null,5986,null,5987,null,5988,null,5989,null,5990,null,5991,null,5992,null,5993,null,5994,null,5995,null,5996,null,5997,null,5998,null,5999,null,6000,null,6001,null,6002,null,6003,null,6004,null,6005,null,6006,null,6007,null,6008,null,6009,null,6010,null,6011,null,6012,null,6013,null,6014,null,6015,null,6016,null,6017,null,6018,null,6019,null,6020,null,6021,null,6022,null,6023,null,6024,null,6025,null,6026,null,6027,null,6028,null,6029,null,6030,null,6031,null,6032,null,6033,null,6034,null,6035,null,6036,null,6037,null,6038,null,6039,null,6040,null,6041,null,6042,null,6043,null,6044,null,6045,null,6046,null,6047,null,6048,null,6049,null,6050,null,6051,null,6052,null,6053,null,6054,null,6055,null,6056,null,6057,null,6058,null,6059,null,6060,null,6061,null,6062,null,6063,null,6064,null,6065,null,6066,null,6067,null,6068,null,6069,null,6070,null,6071,null,6072,null,6073,null,6074,null,6075,null,6076,null,6077,null,6078,null,6079,null,6080,null,6081,null,6082,null,6083,null,6084,null,6085,null,6086,null,6087,null,6088,null,6089,null,6090,null,6091,null,6092,null,6093,null,6094,null,6095,null,6096,null,6097,null,6098,null,6099,null,6100,null,6101,null,6102,null,6103,null,6104,null,6105,null,6106,null,6107,null,6108,null,6109,null,6110,null,6111,null,6112,null,6113,null,6114,null,6115,null,6116,null,6117,null,6118,null,6119,null,6120,null,6121,null,6122,null,6123,null,6124,null,6125,null,6126,null,6127,null,6128,null,6129,null,6130,null,6131,null,6132,null,6133,null,6134,null,6135,null,6136,null,6137,null,6138,null,6139,null,6140,null,6141,null,6142,null,6143,null,6144,null,6145,null,6146,null,6147,null,6148,null,6149,null,6150,null,6151,null,6152,null,6153,null,6154,null,6155,null,6156,null,6157,null,6158,null,6159,null,6160,null,6161,null,6162,null,6163,null,6164,null,6165,null,6166,null,6167,null,6168,null,6169,null,6170,null,6171,null,6172,null,6173,null,6174,null,6175,null,6176,null,6177,null,6178,null,6179,null,6180,null,6181,null,6182,null,6183,null,6184,null,6185,null,6186,null,6187,null,6188,null,6189,null,6190,null,6191,null,6192,null,6193,null,6194,null,6195,null,6196,null,6197,null,6198,null,6199,null,6200,null,6201,null,6202,null,6203,null,6204,null,6205,null,6206,null,6207,null,6208,null,6209,null,6210,null,6211,null,6212,null,6213,null,6214,null,6215,null,6216,null,6217,null,6218,null,6219,null,6220,null,6221,null,6222,null,6223,null,6224,null,6225,null,6226,null,6227,null,6228,null,6229,null,6230,null,6231,null,6232,null,6233,null,6234,null,6235,null,6236,null,6237,null,6238,null,6239,null,6240,null,6241,null,6242,null,6243,null,6244,null,6245,null,6246,null,6247,null,6248,null,6249,null,6250,null,6251,null,6252,null,6253,null,6254,null,6255,null,6256,null,6257,null,6258,null,6259,null,6260,null,6261,null,6262,null,6263,null,6264,null,6265,null,6266,null,6267,null,6268,null,6269,null,6270,null,6271,null,6272,null,6273,null,6274,null,6275,null,6276,null,6277,null,6278,null,6279,null,6280,null,6281,null,6282,null,6283,null,6284,null,6285,null,6286,null,6287,null,6288,null,6289,null,6290,null,6291,null,6292,null,6293,null,6294,null,6295,null,6296,null,6297,null,6298,null,6299,null,6300,null,6301,null,6302,null,6303,null,6304,null,6305,null,6306,null,6307,null,6308,null,6309,null,6310,null,6311,null,6312,null,6313,null,6314,null,6315,null,6316,null,6317,null,6318,null,6319,null,6320,null,6321,null,6322,null,6323,null,6324,null,6325,null,6326,null,6327,null,6328,null,6329,null,6330,null,6331,null,6332,null,6333,null,6334,null,6335,null,6336,null,6337,null,6338,null,6339,null,6340,null,6341,null,6342,null,6343,null,6344,null,6345,null,6346,null,6347,null,6348,null,6349,null,6350,null,6351,null,6352,null,6353,null,6354,null,6355,null,6356,null,6357,null,6358,null,6359,null,6360,null,6361,null,6362,null,6363,null,6364,null,6365,null,6366,null,6367,null,6368,null,6369,null,6370,null,6371,null,6372,null,6373,null,6374,null,6375,null,6376,null,6377,null,6378,null,6379,null,6380,null,6381,null,6382,null,6383,null,6384,null,6385,null,6386,null,6387,null,6388,null,6389,null,6390,null,6391,null,6392,null,6393,null,6394,null,6395,null,6396,null,6397,null,6398,null,6399,null,6400,null,6401,null,6402,null,6403,null,6404,null,6405,null,6406,null,6407,null,6408,null,6409,null,6410,null,6411,null,6412,null,6413,null,6414,null,6415,null,6416,null,6417,null,6418,null,6419,null,6420,null,6421,null,6422,null,6423,null,6424,null,6425,null,6426,null,6427,null,6428,null,6429,null,6430,null,6431,null,6432,null,6433,null,6434,null,6435,null,6436,null,6437,null,6438,null,6439,null,6440,null,6441,null,6442,null,6443,null,6444,null,6445,null,6446,null,6447,null,6448,null,6449,null,6450,null,6451,null,6452,null,6453,null,6454,null,6455,null,6456,null,6457,null,6458,null,6459,null,6460,null,6461,null,6462,null,6463,null,6464,null,6465,null,6466,null,6467,null,6468,null,6469,null,6470,null,6471,null,6472,null,6473,null,6474,null,6475,null,6476,null,6477,null,6478,null,6479,null,6480,null,6481,null,6482,null,6483,null,6484,null,6485,null,6486,null,6487,null,6488,null,6489,null,6490,null,6491,null,6492,null,6493,null,6494,null,6495,null,6496,null,6497,null,6498,null,6499,null,6500,null,6501,null,6502,null,6503,null,6504,null,6505,null,6506,null,6507,null,6508,null,6509,null,6510,null,6511,null,6512,null,6513,null,6514,null,6515,null,6516,null,6517,null,6518,null,6519,null,6520,null,6521,null,6522,null,6523,null,6524,null,6525,null,6526,null,6527,null,6528,null,6529,null,6530,null,6531,null,6532,null,6533,null,6534,null,6535,null,6536,null,6537,null,6538,null,6539,null,6540,null,6541,null,6542,null,6543,null,6544,null,6545,null,6546,null,6547,null,6548,null,6549,null,6550,null,6551,null,6552,null,6553,null,6554,null,6555,null,6556,null,6557,null,6558,null,6559,null,6560,null,6561,null,6562,null,6563,null,6564,null,6565,null,6566,null,6567,null,6568,null,6569,null,6570,null,6571,null,6572,null,6573,null,6574,null,6575,null,6576,null,6577,null,6578,null,6579,null,6580,null,6581,null,6582,null,6583,null,6584,null,6585,null,6586,null,6587,null,6588,null,6589,null,6590,null,6591,null,6592,null,6593,null,6594,null,6595,null,6596,null,6597,null,6598,null,6599,null,6600,null,6601,null,6602,null,6603,null,6604,null,6605,null,6606,null,6607,null,6608,null,6609,null,6610,null,6611,null,6612,null,6613,null,6614,null,6615,null,6616,null,6617,null,6618,null,6619,null,6620,null,6621,null,6622,null,6623,null,6624,null,6625,null,6626,null,6627,null,6628,null,6629,null,6630,null,6631,null,6632,null,6633,null,6634,null,6635,null,6636,null,6637,null,6638,null,6639,null,6640,null,6641,null,6642,null,6643,null,6644,null,6645,null,6646,null,6647,null,6648,null,6649,null,6650,null,6651,null,6652,null,6653,null,6654,null,6655,null,6656,null,6657,null,6658,null,6659,null,6660,null,6661,null,6662,null,6663,null,6664,null,6665,null,6666,null,6667,null,6668,null,6669,null,6670,null,6671,null,6672,null,6673,null,6674,null,6675,null,6676,null,6677,null,6678,null,6679,null,6680,null,6681,null,6682,null,6683,null,6684,null,6685,null,6686,null,6687,null,6688,null,6689,null,6690,null,6691,null,6692,null,6693,null,6694,null,6695,null,6696,null,6697,null,6698,null,6699,null,6700,null,6701,null,6702,null,6703,null,6704,null,6705,null,6706,null,6707,null,6708,null,6709,null,6710,null,6711,null,6712,null,6713,null,6714,null,6715,null,6716,null,6717,null,6718,null,6719,null,6720,null,6721,null,6722,null,6723,null,6724,null,6725,null,6726,null,6727,null,6728,null,6729,null,6730,null,6731,null,6732,null,6733,null,6734,null,6735,null,6736,null,6737,null,6738,null,6739,null,6740,null,6741,null,6742,null,6743,null,6744,null,6745,null,6746,null,6747,null,6748,null,6749,null,6750,null,6751,null,6752,null,6753,null,6754,null,6755,null,6756,null,6757,null,6758,null,6759,null,6760,null,6761,null,6762,null,6763,null,6764,null,6765,null,6766,null,6767,null,6768,null,6769,null,6770,null,6771,null,6772,null,6773,null,6774,null,6775,null,6776,null,6777,null,6778,null,6779,null,6780,null,6781,null,6782,null,6783,null,6784,null,6785,null,6786,null,6787,null,6788,null,6789,null,6790,null,6791,null,6792,null,6793,null,6794,null,6795,null,6796,null,6797,null,6798,null,6799,null,6800,null,6801,null,6802,null,6803,null,6804,null,6805,null,6806,null,6807,null,6808,null,6809,null,6810,null,6811,null,6812,null,6813,null,6814,null,6815,null,6816,null,6817,null,6818,null,6819,null,6820,null,6821,null,6822,null,6823,null,6824,null,6825,null,6826,null,6827,null,6828,null,6829,null,6830,null,6831,null,6832,null,6833,null,6834,null,6835,null,6836,null,6837,null,6838,null,6839,null,6840,null,6841,null,6842,null,6843,null,6844,null,6845,null,6846,null,6847,null,6848,null,6849,null,6850,null,6851,null,6852,null,6853,null,6854,null,6855,null,6856,null,6857,null,6858,null,6859,null,6860,null,6861,null,6862,null,6863,null,6864,null,6865,null,6866,null,6867,null,6868,null,6869,null,6870,null,6871,null,6872,null,6873,null,6874,null,6875,null,6876,null,6877,null,6878,null,6879,null,6880,null,6881,null,6882,null,6883,null,6884,null,6885,null,6886,null,6887,null,6888,null,6889,null,6890,null,6891,null,6892,null,6893,null,6894,null,6895,null,6896,null,6897,null,6898,null,6899,null,6900,null,6901,null,6902,null,6903,null,6904,null,6905,null,6906,null,6907,null,6908,null,6909,null,6910,null,6911,null,6912,null,6913,null,6914,null,6915,null,6916,null,6917,null,6918,null,6919,null,6920,null,6921,null,6922,null,6923,null,6924,null,6925,null,6926,null,6927,null,6928,null,6929,null,6930,null,6931,null,6932,null,6933,null,6934,null,6935,null,6936,null,6937,null,6938,null,6939,null,6940,null,6941,null,6942,null,6943,null,6944,null,6945,null,6946,null,6947,null,6948,null,6949,null,6950,null,6951,null,6952,null,6953,null,6954,null,6955,null,6956,null,6957,null,6958,null,6959,null,6960,null,6961,null,6962,null,6963,null,6964,null,6965,null,6966,null,6967,null,6968,null,6969,null,6970,null,6971,null,6972,null,6973,null,6974,null,6975,null,6976,null,6977,null,6978,null,6979,null,6980,null,6981,null,6982,null,6983,null,6984,null,6985,null,6986,null,6987,null,6988,null,6989,null,6990,null,6991,null,6992,null,6993,null,6994,null,6995,null,6996,null,6997,null,6998,null,6999,null,7000,null,7001,null,7002,null,7003,null,7004,null,7005,null,7006,null,7007,null,7008,null,7009,null,7010,null,7011,null,7012,null,7013,null,7014,null,7015,null,7016,null,7017,null,7018,null,7019,null,7020,null,7021,null,7022,null,7023,null,7024,null,7025,null,7026,null,7027,null,7028,null,7029,null,7030,null,7031,null,7032,null,7033,null,7034,null,7035,null,7036,null,7037,null,7038,null,7039,null,7040,null,7041,null,7042,null,7043,null,7044,null,7045,null,7046,null,7047,null,7048,null,7049,null,7050,null,7051,null,7052,null,7053,null,7054,null,7055,null,7056,null,7057,null,7058,null,7059,null,7060,null,7061,null,7062,null,7063,null,7064,null,7065,null,7066,null,7067,null,7068,null,7069,null,7070,null,7071,null,7072,null,7073,null,7074,null,7075,null,7076,null,7077,null,7078,null,7079,null,7080,null,7081,null,7082,null,7083,null,7084,null,7085,null,7086,null,7087,null,7088,null,7089,null,7090,null,7091,null,7092,null,7093,null,7094,null,7095,null,7096,null,7097,null,7098,null,7099,null,7100,null,7101,null,7102,null,7103,null,7104,null,7105,null,7106,null,7107,null,7108,null,7109,null,7110,null,7111,null,7112,null,7113,null,7114,null,7115,null,7116,null,7117,null,7118,null,7119,null,7120,null,7121,null,7122,null,7123,null,7124,null,7125,null,7126,null,7127,null,7128,null,7129,null,7130,null,7131,null,7132,null,7133,null,7134,null,7135,null,7136,null,7137,null,7138,null,7139,null,7140,null,7141,null,7142,null,7143,null,7144,null,7145,null,7146,null,7147,null,7148,null,7149,null,7150,null,7151,null,7152,null,7153,null,7154,null,7155,null,7156,null,7157,null,7158,null,7159,null,7160,null,7161,null,7162,null,7163,null,7164,null,7165,null,7166,null,7167,null,7168,null,7169,null,7170,null,7171,null,7172,null,7173,null,7174,null,7175,null,7176,null,7177,null,7178,null,7179,null,7180,null,7181,null,7182,null,7183,null,7184,null,7185,null,7186,null,7187,null,7188,null,7189,null,7190,null,7191,null,7192,null,7193,null,7194,null,7195,null,7196,null,7197,null,7198,null,7199,null,7200,null,7201,null,7202,null,7203,null,7204,null,7205,null,7206,null,7207,null,7208,null,7209,null,7210,null,7211,null,7212,null,7213,null,7214,null,7215,null,7216,null,7217,null,7218,null,7219,null,7220,null,7221,null,7222,null,7223,null,7224,null,7225,null,7226,null,7227,null,7228,null,7229,null,7230,null,7231,null,7232,null,7233,null,7234,null,7235,null,7236,null,7237,null,7238,null,7239,null,7240,null,7241,null,7242,null,7243,null,7244,null,7245,null,7246,null,7247,null,7248,null,7249,null,7250,null,7251,null,7252,null,7253,null,7254,null,7255,null,7256,null,7257,null,7258,null,7259,null,7260,null,7261,null,7262,null,7263,null,7264,null,7265,null,7266,null,7267,null,7268,null,7269,null,7270,null,7271,null,7272,null,7273,null,7274,null,7275,null,7276,null,7277,null,7278,null,7279,null,7280,null,7281,null,7282,null,7283,null,7284,null,7285,null,7286,null,7287,null,7288,null,7289,null,7290,null,7291,null,7292,null,7293,null,7294,null,7295,null,7296,null,7297,null,7298,null,7299,null,7300,null,7301,null,7302,null,7303,null,7304,null,7305,null,7306,null,7307,null,7308,null,7309,null,7310,null,7311,null,7312,null,7313,null,7314,null,7315,null,7316,null,7317,null,7318,null,7319,null,7320,null,7321,null,7322,null,7323,null,7324,null,7325,null,7326,null,7327,null,7328,null,7329,null,7330,null,7331,null,7332,null,7333,null,7334,null,7335,null,7336,null,7337,null,7338,null,7339,null,7340,null,7341,null,7342,null,7343,null,7344,null,7345,null,7346,null,7347,null,7348,null,7349,null,7350,null,7351,null,7352,null,7353,null,7354,null,7355,null,7356,null,7357,null,7358,null,7359,null,7360,null,7361,null,7362,null,7363,null,7364,null,7365,null,7366,null,7367,null,7368,null,7369,null,7370,null,7371,null,7372,null,7373,null,7374,null,7375,null,7376,null,7377,null,7378,null,7379,null,7380,null,7381,null,7382,null,7383,null,7384,null,7385,null,7386,null,7387,null,7388,null,7389,null,7390,null,7391,null,7392,null,7393,null,7394,null,7395,null,7396,null,7397,null,7398,null,7399,null,7400,null,7401,null,7402,null,7403,null,7404,null,7405,null,7406,null,7407,null,7408,null,7409,null,7410,null,7411,null,7412,null,7413,null,7414,null,7415,null,7416,null,7417,null,7418,null,7419,null,7420,null,7421,null,7422,null,7423,null,7424,null,7425,null,7426,null,7427,null,7428,null,7429,null,7430,null,7431,null,7432,null,7433,null,7434,null,7435,null,7436,null,7437,null,7438,null,7439,null,7440,null,7441,null,7442,null,7443,null,7444,null,7445,null,7446,null,7447,null,7448,null,7449,null,7450,null,7451,null,7452,null,7453,null,7454,null,7455,null,7456,null,7457,null,7458,null,7459,null,7460,null,7461,null,7462,null,7463,null,7464,null,7465,null,7466,null,7467,null,7468,null,7469,null,7470,null,7471,null,7472,null,7473,null,7474,null,7475,null,7476,null,7477,null,7478,null,7479,null,7480,null,7481,null,7482,null,7483,null,7484,null,7485,null,7486,null,7487,null,7488,null,7489,null,7490,null,7491,null,7492,null,7493,null,7494,null,7495,null,7496,null,7497,null,7498,null,7499,null,7500,null,7501,null,7502,null,7503,null,7504,null,7505,null,7506,null,7507,null,7508,null,7509,null,7510,null,7511,null,7512,null,7513,null,7514,null,7515,null,7516,null,7517,null,7518,null,7519,null,7520,null,7521,null,7522,null,7523,null,7524,null,7525,null,7526,null,7527,null,7528,null,7529,null,7530,null,7531,null,7532,null,7533,null,7534,null,7535,null,7536,null,7537,null,7538,null,7539,null,7540,null,7541,null,7542,null,7543,null,7544,null,7545,null,7546,null,7547,null,7548,null,7549,null,7550,null,7551,null,7552,null,7553,null,7554,null,7555,null,7556,null,7557,null,7558,null,7559,null,7560,null,7561,null,7562,null,7563,null,7564,null,7565,null,7566,null,7567,null,7568,null,7569,null,7570,null,7571,null,7572,null,7573,null,7574,null,7575,null,7576,null,7577,null,7578,null,7579,null,7580,null,7581,null,7582,null,7583,null,7584,null,7585,null,7586,null,7587,null,7588,null,7589,null,7590,null,7591,null,7592,null,7593,null,7594,null,7595,null,7596,null,7597,null,7598,null,7599,null,7600,null,7601,null,7602,null,7603,null,7604,null,7605,null,7606,null,7607,null,7608,null,7609,null,7610,null,7611,null,7612,null,7613,null,7614,null,7615,null,7616,null,7617,null,7618,null,7619,null,7620,null,7621,null,7622,null,7623,null,7624,null,7625,null,7626,null,7627,null,7628,null,7629,null,7630,null,7631,null,7632,null,7633,null,7634,null,7635,null,7636,null,7637,null,7638,null,7639,null,7640,null,7641,null,7642,null,7643,null,7644,null,7645,null,7646,null,7647,null,7648,null,7649,null,7650,null,7651,null,7652,null,7653,null,7654,null,7655,null,7656,null,7657,null,7658,null,7659,null,7660,null,7661,null,7662,null,7663,null,7664,null,7665,null,7666,null,7667,null,7668,null,7669,null,7670,null,7671,null,7672,null,7673,null,7674,null,7675,null,7676,null,7677,null,7678,null,7679,null,7680,null,7681,null,7682,null,7683,null,7684,null,7685,null,7686,null,7687,null,7688,null,7689,null,7690,null,7691,null,7692,null,7693,null,7694,null,7695,null,7696,null,7697,null,7698,null,7699,null,7700,null,7701,null,7702,null,7703,null,7704,null,7705,null,7706,null,7707,null,7708,null,7709,null,7710,null,7711,null,7712,null,7713,null,7714,null,7715,null,7716,null,7717,null,7718,null,7719,null,7720,null,7721,null,7722,null,7723,null,7724,null,7725,null,7726,null,7727,null,7728,null,7729,null,7730,null,7731,null,7732,null,7733,null,7734,null,7735,null,7736,null,7737,null,7738,null,7739,null,7740,null,7741,null,7742,null,7743,null,7744,null,7745,null,7746,null,7747,null,7748,null,7749,null,7750,null,7751,null,7752,null,7753,null,7754,null,7755,null,7756,null,7757,null,7758,null,7759,null,7760,null,7761,null,7762,null,7763,null,7764,null,7765,null,7766,null,7767,null,7768,null,7769,null,7770,null,7771,null,7772,null,7773,null,7774,null,7775,null,7776,null,7777,null,7778,null,7779,null,7780,null,7781,null,7782,null,7783,null,7784,null,7785,null,7786,null,7787,null,7788,null,7789,null,7790,null,7791,null,7792,null,7793,null,7794,null,7795,null,7796,null,7797,null,7798,null,7799,null,7800,null,7801,null,7802,null,7803,null,7804,null,7805,null,7806,null,7807,null,7808,null,7809,null,7810,null,7811,null,7812,null,7813,null,7814,null,7815,null,7816,null,7817,null,7818,null,7819,null,7820,null,7821,null,7822,null,7823,null,7824,null,7825,null,7826,null,7827,null,7828,null,7829,null,7830,null,7831,null,7832,null,7833,null,7834,null,7835,null,7836,null,7837,null,7838,null,7839,null,7840,null,7841,null,7842,null,7843,null,7844,null,7845,null,7846,null,7847,null,7848,null,7849,null,7850,null,7851,null,7852,null,7853,null,7854,null,7855,null,7856,null,7857,null,7858,null,7859,null,7860,null,7861,null,7862,null,7863,null,7864,null,7865,null,7866,null,7867,null,7868,null,7869,null,7870,null,7871,null,7872,null,7873,null,7874,null,7875,null,7876,null,7877,null,7878,null,7879,null,7880,null,7881,null,7882,null,7883,null,7884,null,7885,null,7886,null,7887,null,7888,null,7889,null,7890,null,7891,null,7892,null,7893,null,7894,null,7895,null,7896,null,7897,null,7898,null,7899,null,7900,null,7901,null,7902,null,7903,null,7904,null,7905,null,7906,null,7907,null,7908,null,7909,null,7910,null,7911,null,7912,null,7913,null,7914,null,7915,null,7916,null,7917,null,7918,null,7919,null,7920,null,7921,null,7922,null,7923,null,7924,null,7925,null,7926,null,7927,null,7928,null,7929,null,7930,null,7931,null,7932,null,7933,null,7934,null,7935,null,7936,null,7937,null,7938,null,7939,null,7940,null,7941,null,7942,null,7943,null,7944,null,7945,null,7946,null,7947,null,7948,null,7949,null,7950,null,7951,null,7952,null,7953,null,7954,null,7955,null,7956,null,7957,null,7958,null,7959,null,7960,null,7961,null,7962,null,7963,null,7964,null,7965,null,7966,null,7967,null,7968,null,7969,null,7970,null,7971,null,7972,null,7973,null,7974,null,7975,null,7976,null,7977,null,7978,null,7979,null,7980,null,7981,null,7982,null,7983,null,7984,null,7985,null,7986,null,7987,null,7988,null,7989,null,7990,null,7991,null,7992,null,7993,null,7994,null,7995,null,7996,null,7997,null,7998,null,7999,null,8000,null,8001,null,8002,null,8003,null,8004,null,8005,null,8006,null,8007,null,8008,null,8009,null,8010,null,8011,null,8012,null,8013,null,8014,null,8015,null,8016,null,8017,null,8018,null,8019,null,8020,null,8021,null,8022,null,8023,null,8024,null,8025,null,8026,null,8027,null,8028,null,8029,null,8030,null,8031,null,8032,null,8033,null,8034,null,8035,null,8036,null,8037,null,8038,null,8039,null,8040,null,8041,null,8042,null,8043,null,8044,null,8045,null,8046,null,8047,null,8048,null,8049,null,8050,null,8051,null,8052,null,8053,null,8054,null,8055,null,8056,null,8057,null,8058,null,8059,null,8060,null,8061,null,8062,null,8063,null,8064,null,8065,null,8066,null,8067,null,8068,null,8069,null,8070,null,8071,null,8072,null,8073,null,8074,null,8075,null,8076,null,8077,null,8078,null,8079,null,8080,null,8081,null,8082,null,8083,null,8084,null,8085,null,8086,null,8087,null,8088,null,8089,null,8090,null,8091,null,8092,null,8093,null,8094,null,8095,null,8096,null,8097,null,8098,null,8099,null,8100,null,8101,null,8102,null,8103,null,8104,null,8105,null,8106,null,8107,null,8108,null,8109,null,8110,null,8111,null,8112,null,8113,null,8114,null,8115,null,8116,null,8117,null,8118,null,8119,null,8120,null,8121,null,8122,null,8123,null,8124,null,8125,null,8126,null,8127,null,8128,null,8129,null,8130,null,8131,null,8132,null,8133,null,8134,null,8135,null,8136,null,8137,null,8138,null,8139,null,8140,null,8141,null,8142,null,8143,null,8144,null,8145,null,8146,null,8147,null,8148,null,8149,null,8150,null,8151,null,8152,null,8153,null,8154,null,8155,null,8156,null,8157,null,8158,null,8159,null,8160,null,8161,null,8162,null,8163,null,8164,null,8165,null,8166,null,8167,null,8168,null,8169,null,8170,null,8171,null,8172,null,8173,null,8174,null,8175,null,8176,null,8177,null,8178,null,8179,null,8180,null,8181,null,8182,null,8183,null,8184,null,8185,null,8186,null,8187,null,8188,null,8189,null,8190,null,8191,null,8192,null,8193,null,8194,null,8195,null,8196,null,8197,null,8198,null,8199,null,8200,null,8201,null,8202,null,8203,null,8204,null,8205,null,8206,null,8207,null,8208,null,8209,null,8210,null,8211,null,8212,null,8213,null,8214,null,8215,null,8216,null,8217,null,8218,null,8219,null,8220,null,8221,null,8222,null,8223,null,8224,null,8225,null,8226,null,8227,null,8228,null,8229,null,8230,null,8231,null,8232,null,8233,null,8234,null,8235,null,8236,null,8237,null,8238,null,8239,null,8240,null,8241,null,8242,null,8243,null,8244,null,8245,null,8246,null,8247,null,8248,null,8249,null,8250,null,8251,null,8252,null,8253,null,8254,null,8255,null,8256,null,8257,null,8258,null,8259,null,8260,null,8261,null,8262,null,8263,null,8264,null,8265,null,8266,null,8267,null,8268,null,8269,null,8270,null,8271,null,8272,null,8273,null,8274,null,8275,null,8276,null,8277,null,8278,null,8279,null,8280,null,8281,null,8282,null,8283,null,8284,null,8285,null,8286,null,8287,null,8288,null,8289,null,8290,null,8291,null,8292,null,8293,null,8294,null,8295,null,8296,null,8297,null,8298,null,8299,null,8300,null,8301,null,8302,null,8303,null,8304,null,8305,null,8306,null,8307,null,8308,null,8309,null,8310,null,8311,null,8312,null,8313,null,8314,null,8315,null,8316,null,8317,null,8318,null,8319,null,8320,null,8321,null,8322,null,8323,null,8324,null,8325,null,8326,null,8327,null,8328,null,8329,null,8330,null,8331,null,8332,null,8333,null,8334,null,8335,null,8336,null,8337,null,8338,null,8339,null,8340,null,8341,null,8342,null,8343,null,8344,null,8345,null,8346,null,8347,null,8348,null,8349,null,8350,null,8351,null,8352,null,8353,null,8354,null,8355,null,8356,null,8357,null,8358,null,8359,null,8360,null,8361,null,8362,null,8363,null,8364,null,8365,null,8366,null,8367,null,8368,null,8369,null,8370,null,8371,null,8372,null,8373,null,8374,null,8375,null,8376,null,8377,null,8378,null,8379,null,8380,null,8381,null,8382,null,8383,null,8384,null,8385,null,8386,null,8387,null,8388,null,8389,null,8390,null,8391,null,8392,null,8393,null,8394,null,8395,null,8396,null,8397,null,8398,null,8399,null,8400,null,8401,null,8402,null,8403,null,8404,null,8405,null,8406,null,8407,null,8408,null,8409,null,8410,null,8411,null,8412,null,8413,null,8414,null,8415,null,8416,null,8417,null,8418,null,8419,null,8420,null,8421,null,8422,null,8423,null,8424,null,8425,null,8426,null,8427,null,8428,null,8429,null,8430,null,8431,null,8432,null,8433,null,8434,null,8435,null,8436,null,8437,null,8438,null,8439,null,8440,null,8441,null,8442,null,8443,null,8444,null,8445,null,8446,null,8447,null,8448,null,8449,null,8450,null,8451,null,8452,null,8453,null,8454,null,8455,null,8456,null,8457,null,8458,null,8459,null,8460,null,8461,null,8462,null,8463,null,8464,null,8465,null,8466,null,8467,null,8468,null,8469,null,8470,null,8471,null,8472,null,8473,null,8474,null,8475,null,8476,null,8477,null,8478,null,8479,null,8480,null,8481,null,8482,null,8483,null,8484,null,8485,null,8486,null,8487,null,8488,null,8489,null,8490,null,8491,null,8492,null,8493,null,8494,null,8495,null,8496,null,8497,null,8498,null,8499,null,8500,null,8501,null,8502,null,8503,null,8504,null,8505,null,8506,null,8507,null,8508,null,8509,null,8510,null,8511,null,8512,null,8513,null,8514,null,8515,null,8516,null,8517,null,8518,null,8519,null,8520,null,8521,null,8522,null,8523,null,8524,null,8525,null,8526,null,8527,null,8528,null,8529,null,8530,null,8531,null,8532,null,8533,null,8534,null,8535,null,8536,null,8537,null,8538,null,8539,null,8540,null,8541,null,8542,null,8543,null,8544,null,8545,null,8546,null,8547,null,8548,null,8549,null,8550,null,8551,null,8552,null,8553,null,8554,null,8555,null,8556,null,8557,null,8558,null,8559,null,8560,null,8561,null,8562,null,8563,null,8564,null,8565,null,8566,null,8567,null,8568,null,8569,null,8570,null,8571,null,8572,null,8573,null,8574,null,8575,null,8576,null,8577,null,8578,null,8579,null,8580,null,8581,null,8582,null,8583,null,8584,null,8585,null,8586,null,8587,null,8588,null,8589,null,8590,null,8591,null,8592,null,8593,null,8594,null,8595,null,8596,null,8597,null,8598,null,8599,null,8600,null,8601,null,8602,null,8603,null,8604,null,8605,null,8606,null,8607,null,8608,null,8609,null,8610,null,8611,null,8612,null,8613,null,8614,null,8615,null,8616,null,8617,null,8618,null,8619,null,8620,null,8621,null,8622,null,8623,null,8624,null,8625,null,8626,null,8627,null,8628,null,8629,null,8630,null,8631,null,8632,null,8633,null,8634,null,8635,null,8636,null,8637,null,8638,null,8639,null,8640,null,8641,null,8642,null,8643,null,8644,null,8645,null,8646,null,8647,null,8648,null,8649,null,8650,null,8651,null,8652,null,8653,null,8654,null,8655,null,8656,null,8657,null,8658,null,8659,null,8660,null,8661,null,8662,null,8663,null,8664,null,8665,null,8666,null,8667,null,8668,null,8669,null,8670,null,8671,null,8672,null,8673,null,8674,null,8675,null,8676,null,8677,null,8678,null,8679,null,8680,null,8681,null,8682,null,8683,null,8684,null,8685,null,8686,null,8687,null,8688,null,8689,null,8690,null,8691,null,8692,null,8693,null,8694,null,8695,null,8696,null,8697,null,8698,null,8699,null,8700,null,8701,null,8702,null,8703,null,8704,null,8705,null,8706,null,8707,null,8708,null,8709,null,8710,null,8711,null,8712,null,8713,null,8714,null,8715,null,8716,null,8717,null,8718,null,8719,null,8720,null,8721,null,8722,null,8723,null,8724,null,8725,null,8726,null,8727,null,8728,null,8729,null,8730,null,8731,null,8732,null,8733,null,8734,null,8735,null,8736,null,8737,null,8738,null,8739,null,8740,null,8741,null,8742,null,8743,null,8744,null,8745,null,8746,null,8747,null,8748,null,8749,null,8750,null,8751,null,8752,null,8753,null,8754,null,8755,null,8756,null,8757,null,8758,null,8759,null,8760,null,8761,null,8762,null,8763,null,8764,null,8765,null,8766,null,8767,null,8768,null,8769,null,8770,null,8771,null,8772,null,8773,null,8774,null,8775,null,8776,null,8777,null,8778,null,8779,null,8780,null,8781,null,8782,null,8783,null,8784,null,8785,null,8786,null,8787,null,8788,null,8789,null,8790,null,8791,null,8792,null,8793,null,8794,null,8795,null,8796,null,8797,null,8798,null,8799,null,8800,null,8801,null,8802,null,8803,null,8804,null,8805,null,8806,null,8807,null,8808,null,8809,null,8810,null,8811,null,8812,null,8813,null,8814,null,8815,null,8816,null,8817,null,8818,null,8819,null,8820,null,8821,null,8822,null,8823,null,8824,null,8825,null,8826,null,8827,null,8828,null,8829,null,8830,null,8831,null,8832,null,8833,null,8834,null,8835,null,8836,null,8837,null,8838,null,8839,null,8840,null,8841,null,8842,null,8843,null,8844,null,8845,null,8846,null,8847,null,8848,null,8849,null,8850,null,8851,null,8852,null,8853,null,8854,null,8855,null,8856,null,8857,null,8858,null,8859,null,8860,null,8861,null,8862,null,8863,null,8864,null,8865,null,8866,null,8867,null,8868,null,8869,null,8870,null,8871,null,8872,null,8873,null,8874,null,8875,null,8876,null,8877,null,8878,null,8879,null,8880,null,8881,null,8882,null,8883,null,8884,null,8885,null,8886,null,8887,null,8888,null,8889,null,8890,null,8891,null,8892,null,8893,null,8894,null,8895,null,8896,null,8897,null,8898,null,8899,null,8900,null,8901,null,8902,null,8903,null,8904,null,8905,null,8906,null,8907,null,8908,null,8909,null,8910,null,8911,null,8912,null,8913,null,8914,null,8915,null,8916,null,8917,null,8918,null,8919,null,8920,null,8921,null,8922,null,8923,null,8924,null,8925,null,8926,null,8927,null,8928,null,8929,null,8930,null,8931,null,8932,null,8933,null,8934,null,8935,null,8936,null,8937,null,8938,null,8939,null,8940,null,8941,null,8942,null,8943,null,8944,null,8945,null,8946,null,8947,null,8948,null,8949,null,8950,null,8951,null,8952,null,8953,null,8954,null,8955,null,8956,null,8957,null,8958,null,8959,null,8960,null,8961,null,8962,null,8963,null,8964,null,8965,null,8966,null,8967,null,8968,null,8969,null,8970,null,8971,null,8972,null,8973,null,8974,null,8975,null,8976,null,8977,null,8978,null,8979,null,8980,null,8981,null,8982,null,8983,null,8984,null,8985,null,8986,null,8987,null,8988,null,8989,null,8990,null,8991,null,8992,null,8993,null,8994,null,8995,null,8996,null,8997,null,8998,null,8999,null,9000,null,9001,null,9002,null,9003,null,9004,null,9005,null,9006,null,9007,null,9008,null,9009,null,9010,null,9011,null,9012,null,9013,null,9014,null,9015,null,9016,null,9017,null,9018,null,9019,null,9020,null,9021,null,9022,null,9023,null,9024,null,9025,null,9026,null,9027,null,9028,null,9029,null,9030,null,9031,null,9032,null,9033,null,9034,null,9035,null,9036,null,9037,null,9038,null,9039,null,9040,null,9041,null,9042,null,9043,null,9044,null,9045,null,9046,null,9047,null,9048,null,9049,null,9050,null,9051,null,9052,null,9053,null,9054,null,9055,null,9056,null,9057,null,9058,null,9059,null,9060,null,9061,null,9062,null,9063,null,9064,null,9065,null,9066,null,9067,null,9068,null,9069,null,9070,null,9071,null,9072,null,9073,null,9074,null,9075,null,9076,null,9077,null,9078,null,9079,null,9080,null,9081,null,9082,null,9083,null,9084,null,9085,null,9086,null,9087,null,9088,null,9089,null,9090,null,9091,null,9092,null,9093,null,9094,null,9095,null,9096,null,9097,null,9098,null,9099,null,9100,null,9101,null,9102,null,9103,null,9104,null,9105,null,9106,null,9107,null,9108,null,9109,null,9110,null,9111,null,9112,null,9113,null,9114,null,9115,null,9116,null,9117,null,9118,null,9119,null,9120,null,9121,null,9122,null,9123,null,9124,null,9125,null,9126,null,9127,null,9128,null,9129,null,9130,null,9131,null,9132,null,9133,null,9134,null,9135,null,9136,null,9137,null,9138,null,9139,null,9140,null,9141,null,9142,null,9143,null,9144,null,9145,null,9146,null,9147,null,9148,null,9149,null,9150,null,9151,null,9152,null,9153,null,9154,null,9155,null,9156,null,9157,null,9158,null,9159,null,9160,null,9161,null,9162,null,9163,null,9164,null,9165,null,9166,null,9167,null,9168,null,9169,null,9170,null,9171,null,9172,null,9173,null,9174,null,9175,null,9176,null,9177,null,9178,null,9179,null,9180,null,9181,null,9182,null,9183,null,9184,null,9185,null,9186,null,9187,null,9188,null,9189,null,9190,null,9191,null,9192,null,9193,null,9194,null,9195,null,9196,null,9197,null,9198,null,9199,null,9200,null,9201,null,9202,null,9203,null,9204,null,9205,null,9206,null,9207,null,9208,null,9209,null,9210,null,9211,null,9212,null,9213,null,9214,null,9215,null,9216,null,9217,null,9218,null,9219,null,9220,null,9221,null,9222,null,9223,null,9224,null,9225,null,9226,null,9227,null,9228,null,9229,null,9230,null,9231,null,9232,null,9233,null,9234,null,9235,null,9236,null,9237,null,9238,null,9239,null,9240,null,9241,null,9242,null,9243,null,9244,null,9245,null,9246,null,9247,null,9248,null,9249,null,9250,null,9251,null,9252,null,9253,null,9254,null,9255,null,9256,null,9257,null,9258,null,9259,null,9260,null,9261,null,9262,null,9263,null,9264,null,9265,null,9266,null,9267,null,9268,null,9269,null,9270,null,9271,null,9272,null,9273,null,9274,null,9275,null,9276,null,9277,null,9278,null,9279,null,9280,null,9281,null,9282,null,9283,null,9284,null,9285,null,9286,null,9287,null,9288,null,9289,null,9290,null,9291,null,9292,null,9293,null,9294,null,9295,null,9296,null,9297,null,9298,null,9299,null,9300,null,9301,null,9302,null,9303,null,9304,null,9305,null,9306,null,9307,null,9308,null,9309,null,9310,null,9311,null,9312,null,9313,null,9314,null,9315,null,9316,null,9317,null,9318,null,9319,null,9320,null,9321,null,9322,null,9323,null,9324,null,9325,null,9326,null,9327,null,9328,null,9329,null,9330,null,9331,null,9332,null,9333,null,9334,null,9335,null,9336,null,9337,null,9338,null,9339,null,9340,null,9341,null,9342,null,9343,null,9344,null,9345,null,9346,null,9347,null,9348,null,9349,null,9350,null,9351,null,9352,null,9353,null,9354,null,9355,null,9356,null,9357,null,9358,null,9359,null,9360,null,9361,null,9362,null,9363,null,9364,null,9365,null,9366,null,9367,null,9368,null,9369,null,9370,null,9371,null,9372,null,9373,null,9374,null,9375,null,9376,null,9377,null,9378,null,9379,null,9380,null,9381,null,9382,null,9383,null,9384,null,9385,null,9386,null,9387,null,9388,null,9389,null,9390,null,9391,null,9392,null,9393,null,9394,null,9395,null,9396,null,9397,null,9398,null,9399,null,9400,null,9401,null,9402,null,9403,null,9404,null,9405,null,9406,null,9407,null,9408,null,9409,null,9410,null,9411,null,9412,null,9413,null,9414,null,9415,null,9416,null,9417,null,9418,null,9419,null,9420,null,9421,null,9422,null,9423,null,9424,null,9425,null,9426,null,9427,null,9428,null,9429,null,9430,null,9431,null,9432,null,9433,null,9434,null,9435,null,9436,null,9437,null,9438,null,9439,null,9440,null,9441,null,9442,null,9443,null,9444,null,9445,null,9446,null,9447,null,9448,null,9449,null,9450,null,9451,null,9452,null,9453,null,9454,null,9455,null,9456,null,9457,null,9458,null,9459,null,9460,null,9461,null,9462,null,9463,null,9464,null,9465,null,9466,null,9467,null,9468,null,9469,null,9470,null,9471,null,9472,null,9473,null,9474,null,9475,null,9476,null,9477,null,9478,null,9479,null,9480,null,9481,null,9482,null,9483,null,9484,null,9485,null,9486,null,9487,null,9488,null,9489,null,9490,null,9491,null,9492,null,9493,null,9494,null,9495,null,9496,null,9497,null,9498,null,9499,null,9500,null,9501,null,9502,null,9503,null,9504,null,9505,null,9506,null,9507,null,9508,null,9509,null,9510,null,9511,null,9512,null,9513,null,9514,null,9515,null,9516,null,9517,null,9518,null,9519,null,9520,null,9521,null,9522,null,9523,null,9524,null,9525,null,9526,null,9527,null,9528,null,9529,null,9530,null,9531,null,9532,null,9533,null,9534,null,9535,null,9536,null,9537,null,9538,null,9539,null,9540,null,9541,null,9542,null,9543,null,9544,null,9545,null,9546,null,9547,null,9548,null,9549,null,9550,null,9551,null,9552,null,9553,null,9554,null,9555,null,9556,null,9557,null,9558,null,9559,null,9560,null,9561,null,9562,null,9563,null,9564,null,9565,null,9566,null,9567,null,9568,null,9569,null,9570,null,9571,null,9572,null,9573,null,9574,null,9575,null,9576,null,9577,null,9578,null,9579,null,9580,null,9581,null,9582,null,9583,null,9584,null,9585,null,9586,null,9587,null,9588,null,9589,null,9590,null,9591,null,9592,null,9593,null,9594,null,9595,null,9596,null,9597,null,9598,null,9599,null,9600,null,9601,null,9602,null,9603,null,9604,null,9605,null,9606,null,9607,null,9608,null,9609,null,9610,null,9611,null,9612,null,9613,null,9614,null,9615,null,9616,null,9617,null,9618,null,9619,null,9620,null,9621,null,9622,null,9623,null,9624,null,9625,null,9626,null,9627,null,9628,null,9629,null,9630,null,9631,null,9632,null,9633,null,9634,null,9635,null,9636,null,9637,null,9638,null,9639,null,9640,null,9641,null,9642,null,9643,null,9644,null,9645,null,9646,null,9647,null,9648,null,9649,null,9650,null,9651,null,9652,null,9653,null,9654,null,9655,null,9656,null,9657,null,9658,null,9659,null,9660,null,9661,null,9662,null,9663,null,9664,null,9665,null,9666,null,9667,null,9668,null,9669,null,9670,null,9671,null,9672,null,9673,null,9674,null,9675,null,9676,null,9677,null,9678,null,9679,null,9680,null,9681,null,9682,null,9683,null,9684,null,9685,null,9686,null,9687,null,9688,null,9689,null,9690,null,9691,null,9692,null,9693,null,9694,null,9695,null,9696,null,9697,null,9698,null,9699,null,9700,null,9701,null,9702,null,9703,null,9704,null,9705,null,9706,null,9707,null,9708,null,9709,null,9710,null,9711,null,9712,null,9713,null,9714,null,9715,null,9716,null,9717,null,9718,null,9719,null,9720,null,9721,null,9722,null,9723,null,9724,null,9725,null,9726,null,9727,null,9728,null,9729,null,9730,null,9731,null,9732,null,9733,null,9734,null,9735,null,9736,null,9737,null,9738,null,9739,null,9740,null,9741,null,9742,null,9743,null,9744,null,9745,null,9746,null,9747,null,9748,null,9749,null,9750,null,9751,null,9752,null,9753,null,9754,null,9755,null,9756,null,9757,null,9758,null,9759,null,9760,null,9761,null,9762,null,9763,null,9764,null,9765,null,9766,null,9767,null,9768,null,9769,null,9770,null,9771,null,9772,null,9773,null,9774,null,9775,null,9776,null,9777,null,9778,null,9779,null,9780,null,9781,null,9782,null,9783,null,9784,null,9785,null,9786,null,9787,null,9788,null,9789,null,9790,null,9791,null,9792,null,9793,null,9794,null,9795,null,9796,null,9797,null,9798,null,9799,null,9800,null,9801,null,9802,null,9803,null,9804,null,9805,null,9806,null,9807,null,9808,null,9809,null,9810,null,9811,null,9812,null,9813,null,9814,null,9815,null,9816,null,9817,null,9818,null,9819,null,9820,null,9821,null,9822,null,9823,null,9824,null,9825,null,9826,null,9827,null,9828,null,9829,null,9830,null,9831,null,9832,null,9833,null,9834,null,9835,null,9836,null,9837,null,9838,null,9839,null,9840,null,9841,null,9842,null,9843,null,9844,null,9845,null,9846,null,9847,null,9848,null,9849,null,9850,null,9851,null,9852,null,9853,null,9854,null,9855,null,9856,null,9857,null,9858,null,9859,null,9860,null,9861,null,9862,null,9863,null,9864,null,9865,null,9866,null,9867,null,9868,null,9869,null,9870,null,9871,null,9872,null,9873,null,9874,null,9875,null,9876,null,9877,null,9878,null,9879,null,9880,null,9881,null,9882,null,9883,null,9884,null,9885,null,9886,null,9887,null,9888,null,9889,null,9890,null,9891,null,9892,null,9893,null,9894,null,9895,null,9896,null,9897,null,9898,null,9899,null,9900,null,9901,null,9902,null,9903,null,9904,null,9905,null,9906,null,9907,null,9908,null,9909,null,9910,null,9911,null,9912,null,9913,null,9914,null,9915,null,9916,null,9917,null,9918,null,9919,null,9920,null,9921,null,9922,null,9923,null,9924,null,9925,null,9926,null,9927,null,9928,null,9929,null,9930,null,9931,null,9932,null,9933,null,9934,null,9935,null,9936,null,9937,null,9938,null,9939,null,9940,null,9941,null,9942,null,9943,null,9944,null,9945,null,9946,null,9947,null,9948,null,9949,null,9950,null,9951,null,9952,null,9953,null,9954,null,9955,null,9956,null,9957,null,9958,null,9959,null,9960,null,9961,null,9962,null,9963,null,9964,null,9965,null,9966,null,9967,null,9968,null,9969,null,9970,null,9971,null,9972,null,9973,null,9974,null,9975,null,9976,null,9977,null,9978,null,9979,null,9980,null,9981,null,9982,null,9983,null,9984,null,9985,null,9986,null,9987,null,9988,null,9989,null,9990,null,9991,null,9992,null,9993,null,9994,null,9995,null,9996,null,9997,null,9998,null,9999]
p: 9998
q: 9999

分析 Time Limit Exceeded 原因：

1. 把 Tree 轉成 array：要遍歷一次 Tree。而且為了保持 index 的特殊意義，需要用 None 在 array 裡佔位置，所以 array 比 Tree 還長。Tree 長得越像 linked list、Tree 的高度越高，要佔的位置就越多。每一層的位置數量，是以 2^n 速度成長（n 是指在 Tree 的哪一層）。以這個 input 而言，應該是在這一步時間爆炸的。

2. 找出 p 和 q 在 array 中的 index：遍歷一次 array

3. 找出 p 和 q 的所有 ancestor，在 array 中的 index：花的時間，跟 Tree 的高度，以及 q、p 在 Tree 的哪一層有關

4. 找出 lowest common ancestor：最糟的情況是 O(m^n)，m 是 p 的所有 ancestor 長度， n 是 q 的所有 ancestor 長度

構想：

1. 幫 Tree 的每個節點加上 parent 屬性

2. 找出 p 和 q 的所有 ancestor

3. 找出 lowest common ancestor

python 3 實作（成功）：

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': 

    # 幫 Tree 的每個節點加上 parent 屬性 

    stack = [] 

    current = root 

    while stack or current: 

        if current: 

            stack.append(current) 

            if current.left: 

                current.left.parent = current 

            current = current.left 

        else: 

            current = stack.pop() 

            if current.right: 

                current.right.parent = current 

            current = current.right 

                 

    # 找出 p 和 q 的所有 ancestor 

    p_ancestor = [p] 

    q_ancestor = [q] 

    while p is not root: 

        p_ancestor.append(p.parent) 

        p = p.parent 

    while q is not root: 

        q_ancestor.append(q.parent) 

        q = q.parent 

   

    # 找出 lowest common ancestor 

    low = p_ancestor 

    high = q_ancestor 

    if len(p_ancestor) < len(q_ancestor): 

        low = q_ancestor 

        high = p_ancestor 

         

    for node in low: 

        if node in high: 

            return node

效能：

Runtime: 76 ms, faster than 48.78% of Python3 online submissions for Lowest Common Ancestor of a Binary Tree.
Memory Usage: 18.4 MB, less than 87.70% of Python3 online submissions for Lowest Common Ancestor of a Binary Tree.

感想：有一種「藉由修改題目而偷作弊」的感覺

參考 Solution Approach 1: Recursive Approach

構想：

在遞迴中使用 flag 紀錄是否找到 p 和 q

自己的 python 3 實作：

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': 

   return self.foundLCA(root, p , q)[2] 

         

def foundLCA(self, root, p , q): 

   isPFound = False 

   isQFound = False 

   ans = None 

 

   if not root: 

        return (isPFound, isQFound, ans) 

             

   if root.left: 

        isPFound, isQFound, ans = self.foundLCA(root.left, p, q) 

   if root.right: 

        result = self.foundLCA(root.right, p, q) 

        if not isPFound: 

            isPFound = result[0] 

        if not isQFound: 

            isQFound = result[1] 

        if not ans: 

            ans = result[2] 

             

   if not isPFound and root is p: 

        isPFound = True 

   elif not isQFound and root is q: 

        isQFound = True 

         

   if not ans and isPFound and isQFound: 

        ans = root 

         

   return (isPFound, isQFound, ans)

效能：

Runtime: 80 ms, faster than 33.62% of Python3 online submissions for Lowest Common Ancestor of a Binary Tree.
Memory Usage: 25.4 MB, less than 46.86% of Python3 online submissions for Lowest Common Ancestor of a Binary Tree.

研究別人的解一

來源：官方的 Approach 1 python 參考解答

別人的 python 實作：

class Solution: 

 

   def __init__(self): 

        # Variable to store LCA node. 

        self.ans = None 

 

   def lowestCommonAncestor(self, root, p, q): 

        """ 

        :type root: TreeNode 

        :type p: TreeNode 

        :type q: TreeNode 

        :rtype: TreeNode 

        """ 

        def recurse_tree(current_node): 

 

            # If reached the end of a branch, return False. 

            if not current_node: 

                return False 

 

            # Left Recursion 

            left = recurse_tree(current_node.left) 

 

            # Right Recursion 

            right = recurse_tree(current_node.right) 

 

            # If the current node is one of p or q 

            mid = current_node == p or current_node == q 

 

            # If any two of the three flags left, right or mid become True. 

            if mid + left + right >= 2: 

                self.ans = current_node 

 

            # Return True if either of the three bool values is True. 

            return mid or left or right 

 

        # Traverse the tree 

        recurse_tree(root) 

        return self.ans

效能：

Runtime: 68 ms, faster than 84.81% of Python3 online submissions for Lowest Common Ancestor of a Binary Tree. Memory Usage: 27.8 MB, less than 13.48% of Python3 online submissions for Lowest Common Ancestor of a Binary Tree.

別人的 Approach 1 解，哪裡好：

flag 不包括多餘的資訊：別人的 flag，不在乎找到的節點是 p 還是 q。反正題目保證 p 和 q 不會是同一個節點，而且 p 和 q 一定有在樹上，所以不用管找到的是哪個節點，只需要管「找到兩個節點了沒」。我的 flag 卻偏偏要多標示「找到的是哪個節點」，而需要多做很多條件判斷。

把 ans 存在 __init__ 裡，就不需要像我那樣，在每次遞迴時還要多傳遞一個 ans 變數。

把 recurse_tree 宣告在 lowestCommonAncestor 裡，就不需要像我那樣，在每次遞迴時還要多傳遞變數 p, q。

用「False 是 0， True 是 1」的特性，計算是否蒐集到了兩個 True，很精簡、巧妙。

擔心：LCA 的 ancestor，會不會存進去 self.ans 裡？擔心的事情不會發生。要搜集到兩個 True 的 flag 才會修改 self.ans，而 LCA 的 ancestor，mid 一定是 False，而 p 和 q 一定會集中在左分枝或右分枝，所以頂多只能搜集到一個 True 的 flag。

研究別人的解二

來源：Python | Recursive

別人的 python 實作：

class Solution: 

   def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': 

        if root is None: 

            return None 

        if root==p or root==q: 

            return root 

        ln=self.lowestCommonAncestor(root.left,p,q) 

        rn=self.lowestCommonAncestor(root.right,p,q) 

        if ln and rn: 

            return root 

        elif ln: 

            return ln 

        else: 

            return rn

效能：

Runtime: 64 ms, faster than 94.35% of Python3 online submissions for Lowest Common Ancestor of a Binary Tree.
Memory Usage: 25.3 MB, less than 57.41% of Python3 online submissions for Lowest Common Ancestor of a Binary Tree.

別人的解，哪裡好：

用節點取代 flag。直接回傳一個節點的 LCA，兩個節點的 LCA 都找到了就是答案。

---

最後更新日期： 2021 年 6 月 25 日