500:
Given that non-persistent arrays support both updates and lookups in constant time, it is natural to ask whether the same is possible with persistent arrays. The following theorem shows that under mild assumptions about the space complexity of the array, lookups must take
1106:
39:. That is, after a value's update in a persistent array, there exist two persistent arrays: one persistent array in which the update is taken into account, and one which is equal to the array before the update.
1894:
1806:
765:
540:
170:
1231:
and the tree of arrays. This tree admits an arbitrary root - not necessarily the initial array. The root may be moved to an arbitrary node of the tree. Changing the root from
1202:
1156:
659:
1739:
2011:
1970:
1668:
1627:
704:
468:
persistent. A fully persistent array may be updated an arbitrary number of times while a partially persistent array may be updated at most once. In our previous example, if
114:
1701:
607:
273:
206:
1543:
869:
627:
1929:
1586:
233:
1514:
1485:
814:
794:
724:
574:
389:
965:
2052:
1251:. Similarly, looking up a value takes time proportional to the distance between the array and the root of its family. Thus, if the same array
1208:
of arrays is thus a set of arrays containing an initial array and all of its descendants. Finally, the tree of a family of arrays is the
824:
The most straightforward implementation of a fully persistent array uses an arbitrary persistent map, whose keys are the numbers from
883:
A fully persistent array may be implemented using an array and the so-called Baker's trick. This implementation is used in the
2080:
1819:
1670:
expected amortized time. By the lower bound from the previous section, this time complexity for lookup is optimal when
395:. The main difference between persistent and non-persistent arrays being that, in non-persistent arrays, the array
1755:
1972:
worst-case time and super-linear space. It remains open whether it is possible to achieve worst-case time
729:
504:
123:
1161:
1115:
632:
1706:
1742:
32:
2127:
1975:
1934:
1632:
1591:
664:
50:
2097:
1673:
579:
246:
179:
1519:
2122:
839:
1209:
612:
1899:
1556:
211:
36:
1490:
1461:
8:
2067:
2046:
799:
779:
709:
559:
1227:
A persistent array using Baker's trick consists of a pair with an actual array called
286:
2076:
2132:
543:
20:
890:
In order to define this implementation, a few other definitions must be given. An
2159:
1101:{\displaystyle \mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})}
872:
726:, the lower bound on the lookup complexity in this partially persistent array is
1752:
Straka showed that the times for both operations can be (slightly) improved to
24:
2153:
1260:
833:
460:
There exist two kinds of persistent arrays. A persistent array may be either
2136:
1553:
In 1989, Dietz gave an implementation of fully persistent arrays using
1255:
may be lookup multiple times, it is more efficient to move the root to
1746:
894:
is an array that is not generated by an update on another array. A
42:
2102:
1259:
before doing the lookup. Finally updating an array only takes
495:
884:
1411:
is already the root, there is nothing to do. Otherwise, let
832:− 1. A persistent map may be implemented using a persistent
542:
time in the worst case, regardless of update time, in the
950:
is initial, or it is the initial array of the parent of
1978:
1937:
1902:
1889:{\displaystyle O((\log \log m)^{2}/\log \log \log m)}
1822:
1758:
1709:
1676:
1635:
1594:
1559:
1522:
1493:
1464:
1164:
1118:
968:
842:
802:
782:
732:
712:
667:
635:
615:
582:
562:
507:
289:
249:
235:
can be retrieved quickly. This operation is called a
214:
182:
126:
53:
2066:
Fillâtre, Jean-Christophe; Conchon, Sylvain (2007).
836:, in which case both updates and lookups would take
391:
can be created quickly. This operation is called an
1749:, one for the entire array and one for each index.
1516:time if the root is the array being looked up, but
2117:Dietz, Paul F. (1989). "Fully persistent arrays".
2005:
1964:
1923:
1888:
1800:
1733:
1695:
1662:
1621:
1580:
1548:
1537:
1508:
1479:
1196:
1150:
1100:
863:
808:
788:
759:
718:
698:
653:
621:
601:
568:
534:
488:and has never been updated before the creation of
383:
267:
227:
200:
164:
108:
2119:Proceedings of the Algorithms and Data Structures
2151:
1777:
661:. Assuming the space complexity of the array is
472:were only partially persistent, the creation of
406:For example, consider the following pseudocode.
2065:
1373:is done recursively using the same definition.
887:module parray.ml by Jean-Christophe Filliâtre.
43:Difference between persistent arrays and arrays
35:with properties similar to a (non-persistent)
1298:the only position whose value differ between
1212:whose nodes are the arrays, and with an edge
871:time. This implementation is optimal for the
476:would be forbidden; however, the creation of
1629:worst-case time, and updates can be done in
796:is the number of elements of the array, and
556:Consider a partially persistent array with
496:Lower Bound on Persistent Array Lookup Time
2075:. New York, NY, USA: ACM. pp. 37–46.
2051:: CS1 maint: location missing publisher (
1811:
2126:
2039:Functional Data Structures and Algorithms
116:is a data structure, with a fixed number
2036:
2032:
2030:
2028:
2026:
1741:. This implementation is related to the
1239:takes time proportional to the depth of
1588:space such that lookups can be done in
1266:Technically, given two adjacent arrays
172:. It is expected that, given the array
2152:
2069:A Persistent Union-find Data Structure
1801:{\displaystyle O(\log \log \min(m,n))}
819:
441:At the end of execution, the value of
2116:
2095:
2023:
1158:an arbitrary sequence of indexes and
2110:
1435:is done by first moving the root to
760:{\displaystyle \Omega (\log \log n)}
535:{\displaystyle \Omega (\log \log n)}
399:is destroyed during the creation of
165:{\displaystyle e_{0},\dots ,e_{n-1}}
1403:Finally, moving the root to a node
1243:. That is, in the distance between
13:
1523:
1204:an arbitrary sequence of value. A
1197:{\displaystyle v_{0},\dots ,v_{m}}
1151:{\displaystyle i_{0},\dots ,i_{m}}
973:
970:
878:
771:
733:
654:{\displaystyle 1<\gamma \leq 2}
508:
58:
55:
14:
2171:
2098:"Persistent-array implementation"
2059:
1337:toward the root. If the label of
1734:{\displaystyle \gamma \in (1,2]}
954:. That is, the initial array of
930:or the descendant of a child of
1549:Expected amortized log-log-time
239:. Furthermore, given the array
23:, and more precisely regarding
16:Computer science data structure
2089:
2006:{\displaystyle O(\log \log m)}
2000:
1982:
1965:{\displaystyle O(\log \log m)}
1959:
1941:
1918:
1906:
1883:
1848:
1829:
1826:
1795:
1792:
1780:
1762:
1728:
1716:
1663:{\displaystyle O(\log \log m)}
1657:
1639:
1622:{\displaystyle O(\log \log m)}
1616:
1598:
1575:
1563:
1532:
1526:
1503:
1497:
1474:
1468:
1380:consists in adding a new node
1357:be the other node of the edge
1095:
1069:
1039:
1013:
858:
846:
754:
736:
699:{\displaystyle O(m\log ^{k}m)}
693:
671:
529:
511:
480:would still be valid. Indeed,
378:
290:
109:{\displaystyle \mathrm {ar} =}
103:
65:
1:
2016:
1816:Straka showed how to achieve
1696:{\displaystyle m=n^{\gamma }}
602:{\displaystyle m=n^{\gamma }}
2096:Filliâtre, Jean-Christophe.
1896:worst-case time and linear (
268:{\displaystyle 0\leq i<n}
201:{\displaystyle 0\leq i<n}
7:
10:
2176:
1538:{\displaystyle \Theta (m)}
816:is the number of updates.
484:is an array distinct from
2013:subject to linear space.
1743:order-maintenance problem
1419:toward the current root,
1384:to the tree, and an edge
864:{\displaystyle O(\log n)}
629:is a constant fulfilling
33:persistent data structure
2037:Straka e, Milan (2013).
1545:time in the worst case.
1439:, changing the label of
1278:closer to the root than
1220:to each of its children
902:is an array of the form
445:is still , the value of
2137:10.1007/3-540-51542-9_8
1812:Worst case log-log-time
1407:is done as follows. If
1317:is done as follows. If
622:{\displaystyle \gamma }
2007:
1966:
1925:
1924:{\displaystyle O(m+n)}
1890:
1802:
1735:
1697:
1664:
1623:
1582:
1581:{\displaystyle O(m+n)}
1539:
1510:
1481:
1198:
1152:
1102:
865:
810:
790:
761:
720:
700:
655:
623:
603:
570:
536:
453:is , and the value of
385:
269:
229:
202:
166:
110:
2008:
1967:
1926:
1891:
1803:
1736:
1698:
1665:
1624:
1583:
1540:
1511:
1482:
1431:. Moving the root to
1369:. The computation of
1309:Accessing an element
1235:to an arbitrary node
1199:
1153:
1103:
866:
811:
791:
762:
721:
701:
656:
624:
609:modifications, where
604:
571:
537:
386:
270:
230:
228:{\displaystyle e_{i}}
203:
167:
111:
1976:
1935:
1900:
1820:
1756:
1707:
1674:
1633:
1592:
1557:
1520:
1509:{\displaystyle O(1)}
1491:
1480:{\displaystyle O(1)}
1462:
1162:
1116:
966:
958:is the unique array
840:
800:
780:
730:
710:
665:
633:
613:
580:
560:
505:
287:
247:
212:
180:
124:
51:
1487:time. Lookups take
820:Worst case log-time
554: —
2121:. pp. 67–74.
2003:
1962:
1921:
1886:
1798:
1731:
1693:
1660:
1619:
1578:
1535:
1506:
1477:
1321:is the root, then
1194:
1148:
1098:
861:
806:
786:
757:
716:
696:
651:
619:
599:
566:
552:
532:
449:is , the value of
381:
265:
225:
198:
162:
106:
2082:978-1-59593-676-9
1427:the other end of
1415:the edge leaving
1353:. Otherwise, let
1333:the edge leaving
1329:. Otherwise, let
809:{\displaystyle m}
789:{\displaystyle n}
776:In this section,
719:{\displaystyle k}
569:{\displaystyle n}
550:
2167:
2141:
2140:
2130:
2114:
2108:
2107:
2093:
2087:
2086:
2074:
2063:
2057:
2056:
2050:
2042:
2034:
2012:
2010:
2009:
2004:
1971:
1969:
1968:
1963:
1930:
1928:
1927:
1922:
1895:
1893:
1892:
1887:
1861:
1856:
1855:
1807:
1805:
1804:
1799:
1740:
1738:
1737:
1732:
1702:
1700:
1699:
1694:
1692:
1691:
1669:
1667:
1666:
1661:
1628:
1626:
1625:
1620:
1587:
1585:
1584:
1579:
1544:
1542:
1541:
1536:
1515:
1513:
1512:
1507:
1486:
1484:
1483:
1478:
1376:The creation of
1282:, the edge from
1203:
1201:
1200:
1195:
1193:
1192:
1174:
1173:
1157:
1155:
1154:
1149:
1147:
1146:
1128:
1127:
1107:
1105:
1104:
1099:
1094:
1093:
1081:
1080:
1038:
1037:
1025:
1024:
976:
870:
868:
867:
862:
815:
813:
812:
807:
795:
793:
792:
787:
766:
764:
763:
758:
725:
723:
722:
717:
705:
703:
702:
697:
686:
685:
660:
658:
657:
652:
628:
626:
625:
620:
608:
606:
605:
600:
598:
597:
575:
573:
572:
567:
555:
544:cell-probe model
541:
539:
538:
533:
390:
388:
387:
384:{\displaystyle }
382:
377:
376:
352:
351:
327:
326:
302:
301:
275:and a new value
274:
272:
271:
266:
234:
232:
231:
226:
224:
223:
207:
205:
204:
199:
171:
169:
168:
163:
161:
160:
136:
135:
115:
113:
112:
107:
102:
101:
77:
76:
61:
29:persistent array
21:computer science
2175:
2174:
2170:
2169:
2168:
2166:
2165:
2164:
2150:
2149:
2145:
2144:
2128:10.1.1.621.1599
2115:
2111:
2094:
2090:
2083:
2072:
2064:
2060:
2044:
2043:
2035:
2024:
2019:
1977:
1974:
1973:
1936:
1933:
1932:
1901:
1898:
1897:
1857:
1851:
1847:
1821:
1818:
1817:
1814:
1757:
1754:
1753:
1708:
1705:
1704:
1687:
1683:
1675:
1672:
1671:
1634:
1631:
1630:
1593:
1590:
1589:
1558:
1555:
1554:
1551:
1521:
1518:
1517:
1492:
1489:
1488:
1463:
1460:
1459:
1447:, and changing
1290:is labelled by
1188:
1184:
1169:
1165:
1163:
1160:
1159:
1142:
1138:
1123:
1119:
1117:
1114:
1113:
1089:
1085:
1076:
1072:
1033:
1029:
1020:
1016:
969:
967:
964:
963:
881:
879:Shallow binding
873:pointer machine
841:
838:
837:
822:
801:
798:
797:
781:
778:
777:
774:
772:Implementations
769:
731:
728:
727:
711:
708:
707:
706:for a constant
681:
677:
666:
663:
662:
634:
631:
630:
614:
611:
610:
593:
589:
581:
578:
577:
561:
558:
557:
553:
506:
503:
502:
498:
439:
366:
362:
341:
337:
316:
312:
297:
293:
288:
285:
284:
248:
245:
244:
219:
215:
213:
210:
209:
181:
178:
177:
150:
146:
131:
127:
125:
122:
121:
91:
87:
72:
68:
54:
52:
49:
48:
45:
25:data structures
17:
12:
11:
5:
2173:
2163:
2162:
2143:
2142:
2109:
2088:
2081:
2058:
2021:
2020:
2018:
2015:
2002:
1999:
1996:
1993:
1990:
1987:
1984:
1981:
1961:
1958:
1955:
1952:
1949:
1946:
1943:
1940:
1920:
1917:
1914:
1911:
1908:
1905:
1885:
1882:
1879:
1876:
1873:
1870:
1867:
1864:
1860:
1854:
1850:
1846:
1843:
1840:
1837:
1834:
1831:
1828:
1825:
1813:
1810:
1797:
1794:
1791:
1788:
1785:
1782:
1779:
1776:
1773:
1770:
1767:
1764:
1761:
1730:
1727:
1724:
1721:
1718:
1715:
1712:
1690:
1686:
1682:
1679:
1659:
1656:
1653:
1650:
1647:
1644:
1641:
1638:
1618:
1615:
1612:
1609:
1606:
1603:
1600:
1597:
1577:
1574:
1571:
1568:
1565:
1562:
1550:
1547:
1534:
1531:
1528:
1525:
1505:
1502:
1499:
1496:
1476:
1473:
1470:
1467:
1423:its label and
1378:ar.update(i,v)
1222:ar.update(i,v)
1191:
1187:
1183:
1180:
1177:
1172:
1168:
1145:
1141:
1137:
1134:
1131:
1126:
1122:
1097:
1092:
1088:
1084:
1079:
1075:
1071:
1068:
1065:
1062:
1059:
1056:
1053:
1050:
1047:
1044:
1041:
1036:
1032:
1028:
1023:
1019:
1015:
1012:
1009:
1006:
1003:
1000:
997:
994:
991:
988:
985:
982:
979:
975:
972:
916:ar.update(i,v)
904:ar.update(i,v)
880:
877:
860:
857:
854:
851:
848:
845:
821:
818:
805:
785:
773:
770:
756:
753:
750:
747:
744:
741:
738:
735:
715:
695:
692:
689:
684:
680:
676:
673:
670:
650:
647:
644:
641:
638:
618:
596:
592:
588:
585:
565:
548:
531:
528:
525:
522:
519:
516:
513:
510:
497:
494:
438:.update(2, 5)
420:.update(0, 8)
408:
380:
375:
372:
369:
365:
361:
358:
355:
350:
347:
344:
340:
336:
333:
330:
325:
322:
319:
315:
311:
308:
305:
300:
296:
292:
279:, a new array
264:
261:
258:
255:
252:
222:
218:
197:
194:
191:
188:
185:
159:
156:
153:
149:
145:
142:
139:
134:
130:
105:
100:
97:
94:
90:
86:
83:
80:
75:
71:
67:
64:
60:
57:
44:
41:
15:
9:
6:
4:
3:
2:
2172:
2161:
2158:
2157:
2155:
2148:
2138:
2134:
2129:
2124:
2120:
2113:
2105:
2104:
2099:
2092:
2084:
2078:
2071:
2070:
2062:
2054:
2048:
2040:
2033:
2031:
2029:
2027:
2022:
2014:
1997:
1994:
1991:
1988:
1985:
1979:
1956:
1953:
1950:
1947:
1944:
1938:
1915:
1912:
1909:
1903:
1880:
1877:
1874:
1871:
1868:
1865:
1862:
1858:
1852:
1844:
1841:
1838:
1835:
1832:
1823:
1809:
1789:
1786:
1783:
1774:
1771:
1768:
1765:
1759:
1750:
1748:
1745:and involves
1744:
1725:
1722:
1719:
1713:
1710:
1688:
1684:
1680:
1677:
1654:
1651:
1648:
1645:
1642:
1636:
1613:
1610:
1607:
1604:
1601:
1595:
1572:
1569:
1566:
1560:
1546:
1529:
1500:
1494:
1471:
1465:
1458:Updates take
1456:
1454:
1450:
1446:
1442:
1438:
1434:
1430:
1426:
1422:
1418:
1414:
1410:
1406:
1401:
1399:
1395:
1391:
1387:
1383:
1379:
1374:
1372:
1368:
1364:
1360:
1356:
1352:
1348:
1344:
1340:
1336:
1332:
1328:
1324:
1320:
1316:
1312:
1307:
1305:
1301:
1297:
1293:
1289:
1285:
1281:
1277:
1273:
1269:
1264:
1262:
1261:constant time
1258:
1254:
1250:
1246:
1242:
1238:
1234:
1230:
1225:
1223:
1219:
1215:
1211:
1207:
1189:
1185:
1181:
1178:
1175:
1170:
1166:
1143:
1139:
1135:
1132:
1129:
1124:
1120:
1111:
1090:
1086:
1082:
1077:
1073:
1066:
1063:
1060:
1057:
1054:
1051:
1048:
1045:
1042:
1034:
1030:
1026:
1021:
1017:
1010:
1007:
1004:
1001:
998:
995:
992:
989:
986:
983:
980:
977:
961:
957:
953:
949:
945:
941:
937:
936:initial array
933:
929:
925:
921:
917:
913:
909:
905:
901:
897:
893:
892:initial array
888:
886:
876:
874:
855:
852:
849:
843:
835:
834:balanced tree
831:
827:
817:
803:
783:
768:
751:
748:
745:
742:
739:
713:
690:
687:
682:
678:
674:
668:
648:
645:
642:
639:
636:
616:
594:
590:
586:
583:
576:elements and
563:
547:
545:
526:
523:
520:
517:
514:
493:
491:
487:
483:
482:updated_array
479:
475:
471:
467:
463:
458:
456:
452:
448:
447:updated_array
444:
437:
436:updated_array
433:
430:
428:.update(1, 3)
427:
423:
419:
415:
414:updated_array
411:
407:
404:
402:
398:
394:
373:
370:
367:
363:
359:
356:
353:
348:
345:
342:
338:
334:
331:
328:
323:
320:
317:
313:
309:
306:
303:
298:
294:
283:with content
282:
278:
262:
259:
256:
253:
250:
242:
238:
220:
216:
195:
192:
189:
186:
183:
176:and an index
175:
157:
154:
151:
147:
143:
140:
137:
132:
128:
119:
98:
95:
92:
88:
84:
81:
78:
73:
69:
62:
40:
38:
34:
30:
26:
22:
2146:
2118:
2112:
2101:
2091:
2068:
2061:
2038:
1931:) space, or
1815:
1751:
1552:
1457:
1452:
1448:
1444:
1440:
1436:
1432:
1428:
1424:
1420:
1416:
1412:
1408:
1404:
1402:
1397:
1396:labelled by
1393:
1389:
1385:
1381:
1377:
1375:
1370:
1366:
1362:
1358:
1354:
1350:
1346:
1342:
1338:
1334:
1330:
1326:
1322:
1318:
1314:
1313:of an array
1310:
1308:
1303:
1299:
1295:
1291:
1287:
1283:
1279:
1275:
1271:
1267:
1265:
1256:
1252:
1248:
1244:
1240:
1236:
1232:
1228:
1226:
1221:
1217:
1213:
1205:
1112:initial and
1109:
959:
955:
951:
947:
943:
939:
938:of an array
935:
931:
927:
923:
922:of an array
919:
915:
911:
907:
903:
899:
898:of an array
895:
891:
889:
882:
829:
825:
823:
775:
549:
499:
489:
485:
481:
477:
473:
469:
465:
461:
459:
454:
450:
446:
442:
440:
435:
431:
429:
425:
421:
417:
413:
409:
405:
400:
396:
392:
280:
276:
240:
236:
208:, the value
173:
120:of elements
117:
46:
28:
18:
474:other_array
451:other_array
422:other_array
243:, an index
2017:References
962:such that
942:is either
926:is either
920:descendant
490:last_array
478:last_array
455:last_array
432:last_array
2123:CiteSeerX
2047:cite book
2041:. Prague.
1995:
1989:
1954:
1948:
1878:
1872:
1866:
1842:
1836:
1775:
1769:
1747:vEB trees
1714:∈
1711:γ
1689:γ
1652:
1646:
1611:
1605:
1524:Θ
1179:…
1133:…
1046:…
853:
749:
743:
734:Ω
688:
646:≤
643:γ
617:γ
595:γ
524:
518:
509:Ω
462:partially
371:−
357:…
321:−
307:…
254:≤
187:≤
155:−
141:…
96:−
82:…
47:An array
2154:Category
1445:(i, ar2)
1294:, where
1365:equals
1361:. Then
1349:equals
1325:equals
1292:(i,ar2)
1274:, with
1108:, with
910:is the
875:model.
551:Theorem
2160:Arrays
2125:
2103:GitHub
2079:
1206:family
934:. The
912:parent
906:, and
393:update
237:lookup
2073:(PDF)
1449:array
1421:(i,v)
1398:(i,v)
1388:from
1345:then
1343:(i,v)
1229:array
1216:from
896:child
885:OCaml
486:array
470:array
466:fully
457:is .
443:array
426:array
418:array
410:array
37:array
31:is a
2077:ISBN
2053:link
1703:for
1327:root
1302:and
1270:and
1247:and
1245:root
1233:root
1210:tree
960:init
918:. A
640:<
260:<
193:<
27:, a
2133:doi
1992:log
1986:log
1951:log
1945:log
1875:log
1869:log
1863:log
1839:log
1833:log
1778:min
1772:log
1766:log
1649:log
1643:log
1608:log
1602:log
1455:.
1451:to
1443:to
1437:ar2
1425:ar2
1394:ar2
1392:to
1382:ar2
1371:ar2
1367:ar2
1355:ar2
1341:is
1304:ar2
1300:ar1
1288:ar2
1286:to
1284:ar1
1280:ar2
1276:ar1
1272:ar2
1268:ar1
946:if
914:of
850:log
828:to
746:log
740:log
679:log
521:log
515:log
464:or
412:=
401:ar2
281:ar2
19:In
2156::
2131:.
2100:.
2049:}}
2045:{{
2025:^
1808:.
1433:ar
1417:ar
1409:ar
1405:ar
1400:.
1390:ar
1363:ar
1347:ar
1335:ar
1323:ar
1319:ar
1315:ar
1306:.
1263:.
1257:ar
1253:ar
1249:ar
1241:ar
1237:ar
1224:.
1218:ar
1110:ar
956:ar
952:ar
948:ar
944:ar
940:ar
932:ar
928:ar
924:ar
908:ar
900:ar
767:.
546:.
492:.
434:=
424:=
416:=
403:.
397:ar
241:ar
174:ar
2147:.
2139:.
2135::
2106:.
2085:.
2055:)
2001:)
1998:m
1983:(
1980:O
1960:)
1957:m
1942:(
1939:O
1919:)
1916:n
1913:+
1910:m
1907:(
1904:O
1884:)
1881:m
1859:/
1853:2
1849:)
1845:m
1830:(
1827:(
1824:O
1796:)
1793:)
1790:n
1787:,
1784:m
1781:(
1763:(
1760:O
1729:]
1726:2
1723:,
1720:1
1717:(
1685:n
1681:=
1678:m
1658:)
1655:m
1640:(
1637:O
1617:)
1614:m
1599:(
1596:O
1576:)
1573:n
1570:+
1567:m
1564:(
1561:O
1533:)
1530:m
1527:(
1504:)
1501:1
1498:(
1495:O
1475:)
1472:1
1469:(
1466:O
1453:v
1441:e
1429:e
1413:e
1386:e
1359:e
1351:v
1339:e
1331:e
1311:i
1296:i
1214:e
1190:m
1186:v
1182:,
1176:,
1171:0
1167:v
1144:m
1140:i
1136:,
1130:,
1125:0
1121:i
1096:)
1091:m
1087:v
1083:,
1078:m
1074:i
1070:(
1067:e
1064:t
1061:a
1058:d
1055:p
1052:u
1049:.
1043:.
1040:)
1035:0
1031:v
1027:,
1022:0
1018:i
1014:(
1011:e
1008:t
1005:a
1002:d
999:p
996:u
993:.
990:t
987:i
984:n
981:i
978:=
974:r
971:a
859:)
856:n
847:(
844:O
830:n
826:0
804:m
784:n
755:)
752:n
737:(
714:k
694:)
691:m
683:k
675:m
672:(
669:O
649:2
637:1
591:n
587:=
584:m
564:n
530:)
527:n
512:(
379:]
374:1
368:n
364:e
360:,
354:,
349:1
346:+
343:i
339:e
335:,
332:v
329:,
324:1
318:i
314:e
310:,
304:,
299:0
295:e
291:[
277:v
263:n
257:i
251:0
221:i
217:e
196:n
190:i
184:0
158:1
152:n
148:e
144:,
138:,
133:0
129:e
118:n
104:]
99:1
93:n
89:e
85:,
79:,
74:0
70:e
66:[
63:=
59:r
56:a
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.