50:), or by taking advantage of a pre-existing ordering in one or both of the join relations. The latter condition, called interesting order, can occur because an input to the join might be produced by an index scan of a tree-based index, another merge join, or some other plan operator that happens to produce output sorted on an appropriate key. Interesting orders need not be serendipitous: the optimizer may seek out this possibility and choose a plan that is suboptimal for a specific preceding operation if it yields an interesting order that one or more downstream nodes can exploit.
1403:
Since the comparison logic is not the central aspect of this algorithm, it is hidden behind a generic comparator and can also consist of several comparison criteria (e.g. multiple columns). The compare function should return if a row is
41:
in each relation which display that value. The key idea of the sort-merge algorithm is to first sort the relations by the join attribute, so that interleaved linear scans will encounter these sets at the same time.
45:
In practice, the most expensive part of performing a sort-merge join is arranging for both inputs to the algorithm to be presented in sorted order. This can be achieved via an explicit sort operation (often an
448:
541:
289:
142:
236:
189:
329:
309:
209:
162:
96:
76:
1588:
Note that this implementation assumes the join attributes are unique, i.e., there is no need to output multiple tuples for a given value of the key.
334:
571:. Generalization to other join types is straightforward. The output of the algorithm will contain only rows contained in the
453:
2378:
37:
The basic problem of a join algorithm is to find, for each distinct value of the join attribute, the set of
548:
31:
245:
2392:
101:
214:
167:
8:
2352:
28:
331:
are not ordered the worst case time cost will contain additional terms of sorting time:
314:
294:
194:
147:
81:
61:
580:
544:
2332:
560:
1477:
Note that a relation in terms of this pseudocode supports some basic operations:
24:
2386:
47:
2327:
443:{\displaystyle O(P_{r}+P_{s}+P_{r}\log(P_{r})+P_{s}\log(P_{s}))}
1038:// Mark position of left row and keep copy of current left row
559:
For simplicity, the algorithm is described in the case of an
38:
1491:// Returns true if relation has a next row (otherwise false)
1563:// Restores the current row index to the marked row index
456:
337:
317:
297:
248:
217:
197:
170:
150:
104:
84:
64:
536:{\displaystyle O(P_{r}\log(P_{r})+P_{s}\log(P_{s}))}
535:
442:
323:
303:
283:
230:
203:
183:
156:
136:
90:
70:
2384:
1605:// Assume that left and right are already sorted
1506:// Returns the next row of the relation (if any)
1521:// Sorts the relation with the given comparator
1469:// Return 1 if leftRow is greater than rightRow
714:// Sort left and right relation with comparator
660:// Ensure that at least one element is present
2379:C# Implementations of Various Join Algorithms
1463:// Return -1 if leftRow is less than rightRow
1583:
1466:// Return 0 if leftRow is equal to rightRow
549:Big O notation – Orders of common functions
27:and is used in the implementation of a
2385:
16:Algorithm used in relational databases
969:// Left row is greater than right row
547:terms outweigh the linear terms, see
1374:// Continue with outer forever loop
1191:// Continue with inner forever loop
1119:// Left row and right row are equal
238:pages memory. In the worst case, a
13:
897:// Left row is less than right row
14:
2404:
2373:
291:I/O operations. In the case that
23:(also known as merge join) is a
1836:// if (left.Key > right.Key)
579:relation and duplicates form a
2345:
1548:// Marks the current row index
1305:// Restore left to stored mark
530:
527:
514:
492:
479:
460:
437:
434:
421:
399:
386:
341:
284:{\displaystyle O(P_{r}+P_{s})}
278:
252:
130:
122:
114:
106:
1:
2338:
753:// Start Merge Join algorithm
554:
53:
1224:// Advance to next right row
993:// Advance to next right row
7:
2321:
1338:// Check if left row exists
1170:// Check if left row exists
1149:// Advance to next left row
921:// Advance to next left row
10:
2409:
137:{\displaystyle |R|<|S|}
32:database management system
1590:
1584:Simple C# implementation
1479:
1418:
585:
537:
444:
325:
305:
285:
232:
205:
185:
158:
138:
92:
72:
1122:// Add rows to result
538:
445:
326:
306:
286:
233:
231:{\displaystyle P_{s}}
206:
186:
184:{\displaystyle P_{r}}
159:
139:
93:
73:
454:
335:
315:
295:
246:
215:
195:
168:
148:
102:
82:
62:
98:be relations where
2353:"Sort-Merge Joins"
1416:than another row:
533:
440:
321:
301:
281:
228:
201:
181:
154:
134:
88:
68:
581:Cartesian product
563:of two relations
324:{\displaystyle S}
304:{\displaystyle R}
204:{\displaystyle S}
191:pages memory and
157:{\displaystyle R}
91:{\displaystyle S}
71:{\displaystyle R}
2400:
2367:
2366:
2364:
2363:
2357:www.dcs.ed.ac.uk
2349:
2333:Nested loop join
2317:
2314:
2311:
2308:
2305:
2302:
2299:
2296:
2293:
2290:
2287:
2284:
2281:
2278:
2275:
2272:
2269:
2266:
2263:
2260:
2257:
2254:
2251:
2248:
2245:
2242:
2239:
2236:
2233:
2230:
2227:
2224:
2221:
2218:
2215:
2212:
2209:
2206:
2203:
2200:
2197:
2194:
2191:
2188:
2185:
2182:
2179:
2176:
2173:
2170:
2167:
2164:
2161:
2158:
2155:
2152:
2149:
2146:
2143:
2140:
2137:
2134:
2131:
2128:
2125:
2122:
2119:
2116:
2113:
2110:
2107:
2104:
2101:
2098:
2095:
2092:
2089:
2086:
2083:
2080:
2077:
2074:
2071:
2068:
2065:
2062:
2059:
2056:
2053:
2050:
2047:
2044:
2041:
2038:
2035:
2032:
2029:
2026:
2023:
2020:
2017:
2014:
2011:
2008:
2005:
2002:
1999:
1996:
1993:
1990:
1987:
1984:
1981:
1978:
1975:
1972:
1969:
1966:
1963:
1960:
1957:
1954:
1951:
1948:
1945:
1942:
1939:
1936:
1933:
1930:
1927:
1924:
1921:
1918:
1915:
1912:
1909:
1906:
1903:
1900:
1897:
1894:
1891:
1888:
1885:
1882:
1879:
1876:
1873:
1870:
1867:
1864:
1861:
1858:
1855:
1852:
1849:
1846:
1843:
1840:
1837:
1834:
1831:
1828:
1825:
1822:
1819:
1816:
1813:
1810:
1807:
1804:
1801:
1798:
1795:
1792:
1789:
1786:
1783:
1780:
1777:
1774:
1771:
1768:
1765:
1762:
1759:
1756:
1753:
1750:
1747:
1744:
1741:
1738:
1735:
1732:
1729:
1726:
1723:
1720:
1717:
1714:
1711:
1708:
1705:
1702:
1699:
1696:
1693:
1690:
1687:
1684:
1681:
1678:
1675:
1672:
1669:
1666:
1663:
1660:
1657:
1654:
1651:
1648:
1645:
1642:
1639:
1636:
1633:
1630:
1627:
1624:
1621:
1618:
1615:
1612:
1609:
1606:
1603:
1600:
1597:
1594:
1579:
1576:
1573:
1570:
1567:
1564:
1561:
1558:
1555:
1552:
1549:
1546:
1543:
1540:
1537:
1534:
1531:
1528:
1525:
1522:
1519:
1516:
1513:
1510:
1507:
1504:
1501:
1498:
1495:
1492:
1489:
1486:
1483:
1473:
1470:
1467:
1464:
1461:
1458:
1455:
1452:
1449:
1446:
1443:
1440:
1437:
1434:
1431:
1428:
1425:
1422:
1399:
1396:
1393:
1390:
1387:
1384:
1381:
1378:
1375:
1372:
1369:
1366:
1363:
1362:outerForeverLoop
1360:
1357:
1354:
1351:
1348:
1345:
1342:
1339:
1336:
1333:
1330:
1327:
1324:
1321:
1318:
1315:
1312:
1309:
1306:
1303:
1300:
1297:
1294:
1291:
1288:
1285:
1282:
1279:
1276:
1273:
1270:
1267:
1264:
1261:
1258:
1257:outerForeverLoop
1255:
1252:
1249:
1246:
1243:
1240:
1237:
1234:
1231:
1228:
1225:
1222:
1219:
1216:
1213:
1210:
1207:
1204:
1201:
1198:
1195:
1192:
1189:
1186:
1183:
1180:
1177:
1174:
1171:
1168:
1165:
1162:
1159:
1156:
1153:
1150:
1147:
1144:
1141:
1138:
1135:
1132:
1129:
1126:
1123:
1120:
1117:
1114:
1111:
1108:
1105:
1102:
1099:
1096:
1093:
1090:
1087:
1084:
1081:
1078:
1075:
1072:
1069:
1066:
1063:
1060:
1057:
1054:
1051:
1048:
1045:
1042:
1039:
1036:
1033:
1030:
1027:
1026:outerForeverLoop
1024:
1021:
1018:
1015:
1012:
1009:
1006:
1003:
1000:
997:
994:
991:
988:
985:
982:
979:
976:
973:
970:
967:
964:
961:
958:
955:
954:outerForeverLoop
952:
949:
946:
943:
940:
937:
934:
931:
928:
925:
922:
919:
916:
913:
910:
907:
904:
901:
898:
895:
892:
889:
886:
883:
880:
877:
874:
871:
868:
865:
862:
859:
856:
853:
850:
847:
844:
841:
838:
835:
832:
829:
826:
823:
820:
817:
814:
811:
808:
805:
802:
799:
796:
793:
792:outerForeverLoop
790:
787:
784:
781:
778:
775:
772:
769:
766:
763:
760:
757:
754:
751:
748:
745:
742:
739:
736:
733:
730:
727:
724:
721:
718:
715:
712:
709:
706:
703:
700:
697:
694:
691:
688:
685:
682:
679:
676:
673:
670:
667:
664:
661:
658:
655:
652:
649:
646:
643:
640:
637:
634:
631:
628:
625:
622:
619:
616:
613:
610:
607:
604:
601:
598:
595:
592:
589:
542:
540:
539:
534:
526:
525:
507:
506:
491:
490:
472:
471:
449:
447:
446:
441:
433:
432:
414:
413:
398:
397:
379:
378:
366:
365:
353:
352:
330:
328:
327:
322:
310:
308:
307:
302:
290:
288:
287:
282:
277:
276:
264:
263:
237:
235:
234:
229:
227:
226:
210:
208:
207:
202:
190:
188:
187:
182:
180:
179:
163:
161:
160:
155:
143:
141:
140:
135:
133:
125:
117:
109:
97:
95:
94:
89:
77:
75:
74:
69:
2408:
2407:
2403:
2402:
2401:
2399:
2398:
2397:
2393:Join algorithms
2383:
2382:
2376:
2371:
2370:
2361:
2359:
2351:
2350:
2346:
2341:
2324:
2319:
2318:
2315:
2312:
2309:
2306:
2303:
2300:
2297:
2294:
2291:
2288:
2285:
2282:
2279:
2276:
2273:
2270:
2267:
2264:
2261:
2258:
2255:
2252:
2249:
2246:
2243:
2240:
2237:
2234:
2231:
2228:
2225:
2222:
2219:
2216:
2213:
2210:
2207:
2204:
2201:
2198:
2195:
2192:
2189:
2186:
2183:
2180:
2177:
2174:
2171:
2168:
2165:
2162:
2159:
2156:
2153:
2150:
2147:
2144:
2141:
2138:
2135:
2132:
2129:
2126:
2123:
2120:
2117:
2114:
2111:
2108:
2105:
2102:
2099:
2096:
2093:
2090:
2087:
2084:
2081:
2078:
2075:
2072:
2069:
2066:
2063:
2060:
2057:
2054:
2051:
2048:
2045:
2042:
2039:
2036:
2033:
2030:
2027:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
2003:
2000:
1997:
1994:
1991:
1988:
1985:
1982:
1979:
1976:
1973:
1970:
1967:
1964:
1961:
1958:
1955:
1952:
1949:
1946:
1943:
1940:
1937:
1934:
1931:
1928:
1925:
1922:
1919:
1916:
1913:
1910:
1907:
1904:
1901:
1898:
1895:
1892:
1889:
1886:
1883:
1880:
1877:
1874:
1871:
1868:
1865:
1862:
1859:
1856:
1853:
1850:
1847:
1844:
1841:
1838:
1835:
1832:
1829:
1826:
1823:
1820:
1817:
1814:
1811:
1808:
1805:
1802:
1799:
1796:
1793:
1790:
1787:
1784:
1781:
1778:
1775:
1772:
1769:
1766:
1763:
1760:
1757:
1754:
1751:
1748:
1745:
1742:
1739:
1736:
1733:
1730:
1727:
1724:
1721:
1718:
1715:
1712:
1709:
1706:
1703:
1700:
1697:
1694:
1691:
1688:
1685:
1682:
1679:
1676:
1673:
1670:
1667:
1664:
1661:
1658:
1655:
1652:
1649:
1646:
1643:
1640:
1637:
1634:
1631:
1628:
1625:
1622:
1619:
1616:
1613:
1610:
1607:
1604:
1601:
1598:
1595:
1592:
1586:
1581:
1580:
1577:
1574:
1571:
1568:
1565:
1562:
1559:
1556:
1553:
1550:
1547:
1544:
1541:
1538:
1535:
1532:
1529:
1526:
1523:
1520:
1517:
1514:
1511:
1508:
1505:
1502:
1499:
1496:
1493:
1490:
1487:
1484:
1481:
1475:
1474:
1471:
1468:
1465:
1462:
1459:
1456:
1453:
1450:
1447:
1444:
1441:
1438:
1435:
1432:
1429:
1426:
1423:
1420:
1401:
1400:
1397:
1394:
1391:
1388:
1385:
1382:
1379:
1376:
1373:
1370:
1367:
1364:
1361:
1358:
1355:
1352:
1349:
1346:
1343:
1340:
1337:
1334:
1331:
1328:
1325:
1322:
1319:
1316:
1313:
1310:
1307:
1304:
1301:
1298:
1295:
1292:
1289:
1286:
1283:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1259:
1256:
1253:
1250:
1247:
1244:
1241:
1238:
1235:
1232:
1229:
1226:
1223:
1220:
1217:
1214:
1211:
1208:
1205:
1202:
1199:
1196:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1172:
1169:
1166:
1163:
1160:
1157:
1154:
1151:
1148:
1145:
1142:
1139:
1136:
1133:
1130:
1127:
1124:
1121:
1118:
1115:
1112:
1109:
1106:
1103:
1100:
1097:
1094:
1091:
1088:
1085:
1082:
1079:
1076:
1073:
1070:
1067:
1064:
1061:
1058:
1055:
1052:
1049:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
1004:
1001:
998:
995:
992:
989:
986:
983:
980:
977:
974:
971:
968:
965:
962:
959:
956:
953:
950:
947:
944:
941:
938:
935:
932:
929:
926:
923:
920:
917:
914:
911:
908:
905:
902:
899:
896:
893:
890:
887:
884:
881:
878:
875:
872:
869:
866:
863:
860:
857:
854:
851:
848:
845:
842:
839:
836:
833:
830:
827:
824:
821:
818:
815:
812:
809:
806:
803:
800:
797:
794:
791:
788:
785:
782:
779:
776:
773:
770:
767:
764:
761:
758:
755:
752:
749:
746:
743:
740:
737:
734:
731:
728:
725:
722:
719:
716:
713:
710:
707:
704:
701:
698:
695:
692:
689:
686:
683:
680:
677:
674:
671:
668:
665:
662:
659:
656:
653:
650:
647:
644:
641:
638:
635:
632:
629:
626:
623:
620:
617:
614:
611:
608:
605:
602:
599:
596:
593:
590:
587:
557:
521:
517:
502:
498:
486:
482:
467:
463:
455:
452:
451:
450:, which equals
428:
424:
409:
405:
393:
389:
374:
370:
361:
357:
348:
344:
336:
333:
332:
316:
313:
312:
296:
293:
292:
272:
268:
259:
255:
247:
244:
243:
240:sort-merge join
222:
218:
216:
213:
212:
196:
193:
192:
175:
171:
169:
166:
165:
149:
146:
145:
129:
121:
113:
105:
103:
100:
99:
83:
80:
79:
63:
60:
59:
56:
21:sort-merge join
17:
12:
11:
5:
2406:
2396:
2395:
2375:
2374:External links
2372:
2369:
2368:
2343:
2342:
2340:
2337:
2336:
2335:
2330:
2323:
2320:
1591:
1585:
1582:
1480:
1419:
586:
556:
553:
532:
529:
524:
520:
516:
513:
510:
505:
501:
497:
494:
489:
485:
481:
478:
475:
470:
466:
462:
459:
439:
436:
431:
427:
423:
420:
417:
412:
408:
404:
401:
396:
392:
388:
385:
382:
377:
373:
369:
364:
360:
356:
351:
347:
343:
340:
320:
300:
280:
275:
271:
267:
262:
258:
254:
251:
225:
221:
200:
178:
174:
153:
132:
128:
124:
120:
116:
112:
108:
87:
67:
55:
52:
25:join algorithm
15:
9:
6:
4:
3:
2:
2405:
2394:
2391:
2390:
2388:
2381:
2380:
2358:
2354:
2348:
2344:
2334:
2331:
2329:
2326:
2325:
1589:
1478:
1417:
1415:
1411:
1407:
1326:markedLeftRow
1281:markedLeftRow
1053:markedLeftRow
584:
582:
578:
574:
570:
566:
562:
552:
550:
546:
522:
518:
511:
508:
503:
499:
495:
487:
483:
476:
473:
468:
464:
457:
429:
425:
418:
415:
410:
406:
402:
394:
390:
383:
380:
375:
371:
367:
362:
358:
354:
349:
345:
338:
318:
298:
273:
269:
265:
260:
256:
249:
241:
223:
219:
198:
176:
172:
151:
126:
118:
110:
85:
65:
51:
49:
48:external sort
43:
40:
35:
33:
30:
26:
22:
2377:
2360:. Retrieved
2356:
2347:
1587:
1476:
1413:
1409:
1405:
1402:
576:
572:
568:
564:
558:
545:linearithmic
242:will run in
239:
57:
44:
36:
20:
18:
1566:restoreMark
1518:RelationRow
1448:RelationRow
1436:RelationRow
1314:restoreMark
2362:2022-11-02
2339:References
1683:&&
1536:Comparator
1530:comparator
1269:comparator
1083:comparator
861:comparator
819:comparator
747:comparator
729:comparator
636:Comparator
630:comparator
561:inner join
555:Pseudocode
54:Complexity
29:relational
2328:Hash join
2205:WriteLine
2136:IsPastEnd
1695:IsPastEnd
1677:IsPastEnd
1599:MergeJoin
1482:interface
1414:bigger(1)
512:
477:
419:
384:
2387:Category
2322:See also
2274:Relation
2223:Relation
2148:position
2064:position
2040:position
2025:position
2001:position
1956:position
1950:Position
1932:position
1875:Relation
1656:Relation
1644:Relation
1632:Relation
1623:Relation
1614:Relation
1485:Relation
1442:rightRow
1421:function
1410:equal(0)
1406:less(-1)
1287:rightRow
1227:rightRow
1143:rightRow
1101:rightRow
996:rightRow
879:rightRow
837:rightRow
774:rightRow
654:Relation
624:Relation
612:Relation
588:function
211:fits in
164:fits in
2199:Console
2178:foreach
1986:Advance
1881:private
1845:Advance
1827:Advance
1779:Advance
1767:Advance
1503:boolean
1494:hasNext
1430:leftRow
1424:compare
1350:leftRow
1320:leftRow
1275:compare
1215:hasNext
1182:leftRow
1152:leftRow
1137:leftRow
1095:leftRow
1089:compare
1059:leftRow
984:hasNext
924:leftRow
912:hasNext
873:leftRow
867:compare
831:leftRow
825:compare
756:leftRow
696:hasNext
678:hasNext
2271:public
2220:public
2163:public
2154:ENDPOS
2145:return
2130:public
2085:public
2073:return
2052:return
2046:ENDPOS
2031:ENDPOS
1980:public
1962:public
1944:public
1926:public
1911:ENDPOS
1902:public
1869:public
1857:output
1854:return
1737:output
1647:output
1611:static
1608:public
1593:public
1457:number
1395:result
1392:return
1125:result
708:result
705:return
645:result
39:tuples
2169:Print
2055:false
2013:Count
1971:=>
1953:=>
1905:const
1872:class
1839:right
1809:right
1773:right
1722:right
1689:right
1662:while
1635:right
1617:Merge
1596:class
1377:break
1359:break
1254:break
1233:right
1209:right
1194:break
1077:while
1062:while
1023:break
1002:right
978:right
951:break
813:while
798:while
780:right
735:right
690:right
618:right
597:Merge
577:right
569:right
2307:>
2301:<
2298:List
2289:list
2283:this
2262:list
2256:list
2250:this
2241:list
2238:>
2232:<
2229:List
2193:list
2166:void
2133:bool
2109:list
2088:void
2076:true
2007:list
1983:bool
1974:list
1896:list
1893:>
1887:<
1884:List
1833:else
1821:left
1806:<
1797:left
1788:else
1761:left
1749:left
1710:left
1671:left
1626:left
1575:void
1560:void
1551:mark
1545:void
1524:sort
1509:next
1368:else
1332:else
1308:left
1248:else
1239:next
1164:next
1158:left
1068:true
1047:mark
1041:left
1017:else
1008:next
963:else
945:else
936:next
930:left
906:left
885:<
804:true
786:next
768:next
762:left
741:sort
723:sort
717:left
672:left
606:left
600:Join
591:Sort
575:and
573:left
567:and
565:left
543:(as
311:and
119:<
78:and
58:Let
19:The
2310:();
2304:int
2295:new
2235:int
2211:key
2187:key
2184:int
2121:key
2115:Add
2100:key
2097:int
2091:Add
1968:Key
1965:int
1947:int
1929:int
1908:int
1890:int
1848:();
1830:();
1815:Key
1803:Key
1782:();
1770:();
1755:Key
1743:Add
1728:Key
1716:Key
1698:())
1659:();
1653:new
1412:or
1218:())
1131:add
987:())
915:())
699:())
651:new
551:).
509:log
474:log
416:log
381:log
2389::
2355:.
2277:()
2214:);
2190:in
2172:()
2151:==
2139:()
2124:);
2067:++
2028:==
2022:||
2004:==
1995:if
1989:()
1791:if
1758:);
1719:==
1704:if
1680:()
1569:()
1554:()
1512:()
1497:()
1408:,
1341:if
1317:()
1293:==
1263:if
1242:()
1203:if
1173:if
1167:()
1107:==
1050:()
1011:()
972:if
939:()
900:if
855:if
843:!=
789:()
771:()
684:||
681:()
663:if
657:()
583:.
144:.
34:.
2365:.
2316:}
2313:}
2292:=
2286:.
2280:{
2268:}
2265:;
2259:=
2253:.
2247:{
2244:)
2226:(
2217:}
2208:(
2202:.
2196:)
2181:(
2175:{
2160:}
2157:;
2142:{
2127:}
2118:(
2112:.
2106:{
2103:)
2094:(
2082:}
2079:;
2070:;
2061:}
2058:;
2049:;
2043:=
2037:{
2034:)
2019:1
2016:-
2010:.
1998:(
1992:{
1977:;
1959:;
1941:;
1938:0
1935:=
1923:;
1920:1
1917:-
1914:=
1899:;
1878:{
1866:}
1863:}
1860:;
1851:}
1842:.
1824:.
1818:)
1812:.
1800:.
1794:(
1785:}
1776:.
1764:.
1752:.
1746:(
1740:.
1734:{
1731:)
1725:.
1713:.
1707:(
1701:{
1692:.
1686:!
1674:.
1668:!
1665:(
1650:=
1641:{
1638:)
1629:,
1620:(
1602:{
1578:}
1572::
1557::
1542::
1539:)
1533::
1527:(
1515::
1500::
1488:{
1472:}
1460:{
1454::
1451:)
1445::
1439:,
1433::
1427:(
1398:}
1389:}
1386:}
1383:}
1380:}
1371:{
1365:}
1356:{
1353:)
1347:!
1344:(
1335:{
1329:}
1323:=
1311:.
1302:{
1299:)
1296:0
1290:)
1284:,
1278:(
1272:.
1266:(
1260:}
1251:{
1245:}
1236:.
1230:=
1221:{
1212:.
1206:(
1200:}
1197:}
1188:{
1185:)
1179:!
1176:(
1161:.
1155:=
1146:)
1140:,
1134:(
1128:=
1116:{
1113:)
1110:0
1104:)
1098:,
1092:(
1086:.
1080:(
1074:{
1071:)
1065:(
1056:=
1044:.
1035:}
1032:}
1029:}
1020:{
1014:}
1005:.
999:=
990:{
981:.
975:(
966:{
960:}
957:}
948:{
942:}
933:.
927:=
918:{
909:.
903:(
894:{
891:)
888:0
882:)
876:,
870:(
864:.
858:(
852:{
849:)
846:0
840:)
834:,
828:(
822:.
816:(
810:{
807:)
801:(
795::
783:.
777:=
765:.
759:=
750:)
744:(
738:.
732:)
726:(
720:.
711:}
702:{
693:.
687:!
675:.
669:!
666:(
648:=
642:{
639:)
633::
627:,
621::
615:,
609::
603:(
594:-
531:)
528:)
523:s
519:P
515:(
504:s
500:P
496:+
493:)
488:r
484:P
480:(
469:r
465:P
461:(
458:O
438:)
435:)
430:s
426:P
422:(
411:s
407:P
403:+
400:)
395:r
391:P
387:(
376:r
372:P
368:+
363:s
359:P
355:+
350:r
346:P
342:(
339:O
319:S
299:R
279:)
274:s
270:P
266:+
261:r
257:P
253:(
250:O
224:s
220:P
199:S
177:r
173:P
152:R
131:|
127:S
123:|
115:|
111:R
107:|
86:S
66:R
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.