715:
constraints that make the problem it solves not exactly the stable matching problem. It has the advantage that the students do not need to commit to their preferences at the start of the process, but rather can determine their own preferences as the algorithm progresses, on the basis of head-to-head comparisons between offers that they have received. It is important that this process performs a small number of rounds of proposals, so that it terminates before the start date of the schools, but although high numbers of rounds can occur in theory, they tend not to occur in practice. It has been shown theoretically that, if the Gale–Shapley algorithm needs to be terminated early, after a small number of rounds in which every vacant position makes a new offer, it nevertheless produces matchings that have a high ratio of matched participants to unstable pairs.
706:, a target number of students to admit, and the number of students applying for admission may differ from the sum of the quotas, necessarily causing either some students to remain unmatched or some quotas to remain unfilled. Additionally, preference lists may be incomplete: if a university omits a student from their list, it means they would prefer to leave their quota unfilled than to admit that student, and if a student omits a university from their list, it means they would prefer to remain unadmitted than to go to that university. Nevertheless, it is possible to define stable matchings for this more general problem, to prove that stable matchings always exist, and to apply the same algorithm to find one.
684:: presenting only the topmost alternatives, implying that the bottom alternatives are not acceptable at all. Under complete information, it is sufficient to consider misrepresentations of the form of truncation strategies. However, successful misrepresentation requires knowledge of the other agents' preferences; without such knowledge, misrepresentation can give an agent a worse assignment. Moreover, even after an agent sees the final matching, they cannot deduce a strategy that would guarantee a better outcome in hindsight. This makes the Gale–Shapley algorithm a
200:
180:) where both participants prefer each other to their matched partners. If such a pair exists, the matching is not stable, in the sense that the members of this pair would prefer to leave the system and be matched to each other, possibly leaving other participants unmatched. A stable matching always exists, and the algorithmic problem solved by the Gale–Shapley algorithm is to find one.
676:
for proposers, i.e., no coalition of proposers can coordinate a misrepresentation of their preferences such that all proposers in the coalition are strictly better-off. However, it is possible for some coalition to misrepresent their preferences such that some proposers are better-off, and the others
714:
system. In this process, over the course of the summer before the start of school, applicants receive offers of admission, and must choose in each round of the process whether to accept any new offer (and if so turn down any previous offer that they accepted). The method is complicated by additional
651:
In a reversed form of the algorithm, each round consists of unemployed applicants writing a single job application to their preferred employer, and the employer either accepting the application (possibly firing an existing employee to do so) or rejecting it. This produces a matching that is best for
91:
The stable matching problem seeks to pair up equal numbers of participants of two types, using preferences from each participant. The pairing must be stable: no pair of participants should prefer each other to their assigned match. In each round of the Gale–Shapley algorithm, unmatched participants
639:
There may be many stable matchings for the same system of preferences. This raises the question: which matching is returned by the Gale–Shapley algorithm? Is it the matching better for applicants, for employers, or an intermediate one? As it turns out, the Gale–Shapley algorithm in which employers
561:
At the end, there cannot be an applicant and employer both unmatched. An employer left unmatched at the end of the process must have made an offer to all applicants. But an applicant who receives an offer remains employed for the rest of the process, so there can be no unemployed applicants. Since
426:
time. With these structures it is possible to find an employer with an unfilled position, make an offer from that employer to their next applicant, determine whether the offer is accepted, and update all of the data structures to reflect the results of these steps, in constant time per offer. Once
237:
Each applicant who has received an offer evaluates it against their current position (if they have one). If the applicant is not yet employed, or if they receive an offer from an employer they like better than their current employer, they accept the best new offer and become matched to the new
96:
from the point of view of the proposing participants, who receive their most-preferred pairing consistent with stability. In contrast, the recipients of proposals receive their least-preferred pairing. The algorithm can be implemented to run in time quadratic in the number of participants, and
659:
In both forms of the algorithm, one group of participants proposes matches, and the other group decides whether to accept or reject each proposal. The matching is always best for the group that makes the propositions, and worst for the group that decides how to handle each proposal.
131:
employers, for example), and an ordering for each participant giving their preference for whom to be matched to among the participants of the other type. A matching pairs each participant of one type with a participant of the other type. A matching is
250:
To implement the algorithm efficiently, each employer needs to be able to find its next applicant quickly, and each applicant needs to be able to compare employers quickly. One way to do this is to number each applicant and each employer from 1 to
104:
The stable matching problem, and the Gale–Shapley algorithm solving it, have widespread real-world applications, including matching
American medical students to residencies and French university applicants to schools. For more, see
690:. Moreover, in the Gale–Shapley algorithm, truth-telling is the only strategy that guarantees no regret. The Gale–Shapley algorithm is the only regret-free mechanism in the class of quantile-stable matching mechanisms.
709:
A form of the Gale–Shapley algorithm, performed through a real-world protocol rather than calculated on computers, has been used for coordinating higher education admissions in France since 2018, through the
680:
The Gale–Shapley algorithm is non-truthful for the non-proposing participants. Each may be able to misrepresent their preferences and get a better match. A particular form of manipulation is
92:
of one type propose a match to the next participant on their preference list. Each proposal is accepted if its recipient prefers it to their current match. The resulting procedure is a
672:
from the point of view of the proposing side. This means that no proposer can get a better matching by misrepresenting their preferences. Moreover, the Gale–Shapley algorithm is even
215:
proved that, for any equal number of participants of each type, it is always possible to find a matching in which all pairs are stable. They presented an algorithm to do so. In 1984,
191:. However, this metaphor has been criticized as both sexist and unrealistic: the steps of the algorithm do not accurately reflect typical or even stereotypical human behavior.
640:
make offers to applicants always yields the same stable matching (regardless of the order in which job offers are made), and its choice is the stable matching that is the
234:
In each round, one or more employers with open job positions each make a job offer to the applicant they prefer, among the ones they have not yet already made an offer to.
905:(Master's thesis). National and Kapodistrian University of Athens, Department of History and Philosophy of Science and Department of Informatics and Telecommunications
544:
497:
461:
424:
382:
361:
341:
289:
269:
1323:
Floréen, Patrik; Kaski, Petteri; Polishchuk, Valentin; Suomela, Jukka (August 2009). "Almost stable matchings by truncating the Gale–Shapley algorithm".
310:
indexed by employers, specifying the preference index of the next applicant to whom the employer would send an offer, initially 1 for each employer
219:
observed that essentially the same algorithm had already been in practical use since the early 1950s, as the "Boston Pool algorithm" used by the
320:
A two-dimensional array indexed by an applicant and an employer, specifying the position of that employer in the applicant's preference list
1214:
Huang, Chien-Chung (2006). "Cheating by men in the Gale-Shapley stable matching algorithm". In Azar, Yossi; Erlebach, Thomas (eds.).
724:
85:
698:
In their original work on the problem, Gale and
Shapley considered a more general form of the stable matching problem, suitable for
652:
all applicants and worst for all employers among all stable matchings. These two matchings are the top and bottom elements of the
17:
427:
the algorithm terminates, the resulting matching can be read off from the array of employers for each applicant. There can be
934:
1251:
241:
This process is repeated until all employers have either filled their positions or exhausted their lists of applicants.
220:
187:, using a metaphor of marriage between men and women, and many sources describe the Gale–Shapley algorithm in terms of
77:
1413:
1171:
1137:
939:
841:
813:
699:
123:
The stable matching problem, in its most basic form, takes as input equal numbers of two types of participants (
1017:
1216:
Algorithms – ESA 2006, 14th Annual
European Symposium, Zurich, Switzerland, September 11–13, 2006, Proceedings
106:
238:
employer (possibly leaving a previous employer with an open position). Otherwise, they reject the new offer.
857:
Wagner, Roy (April 2009). "Mathematical marriages: Intercourse between mathematics and semiotic choice".
740:
653:
634:
1052:
859:
562:
the numbers of applicants and job openings are equal, there can also be no open positions remaining.
1403:
745:
300:
1124:
118:
65:
1408:
307:
989:
803:
513:
466:
430:
393:
313:
A one-dimensional array indexed by applicants, specifying their current employer, initially a
897:
685:
1231:
1200:
1147:
1360:
Bhattacharjee, Yudhijit (October 15, 2012). "Economics Nobel honors matchmaking finesse".
8:
1332:
1260:
1188:
1026:
956:
669:
367:
346:
326:
274:
254:
93:
1379:
1362:
1166:
1133:
837:
809:
510:
when measured in terms of the size of the input, two matrices of preferences of size
188:
1371:
1342:
1291:
1270:
1219:
1180:
948:
876:
868:
784:
503:
41:
964:
1375:
1227:
1218:. Lecture Notes in Computer Science. Vol. 4168. Springer. pp. 418–431.
1196:
1143:
1090:(2006). "2.3 Implementing the stable matching algorithm using lists and arrays".
1305:
881:
314:
292:
1346:
1309:
230:"). In terms of job applicants and employers, it can be expressed as follows:
1397:
1162:
1083:
985:
930:
872:
770:
728:
463:
offers before each employer runs out of offers to make, so the total time is
216:
212:
81:
73:
1312:(Invited lecture at the European Symposium of Algorithms). Aalto University.
1087:
1383:
1120:
829:
788:
773:(February 2003). "The origins, history, and design of the resident match".
1126:
Mariages stables et leurs relations avec d'autres problèmes combinatoires
507:
98:
33:
1223:
1132:(in French). Montréal, Quebec: Les Presses de l'Université de Montréal.
1192:
1030:
960:
926:
711:
208:
69:
291:
is the number of employers and applicants, and to store the following
227:
61:
37:
1184:
952:
1013:
Two-Sided
Matching: A Study in Game-Theoretic Modeling and Analysis
1337:
1294:(Working paper). Johns Hopkins University Department of Economics.
1275:
1265:
1246:
731:". Gale had died in 2008, making him ineligible for the prize.
702:. In this problem, each university or college may have its own
199:
226:
The Gale–Shapley algorithm involves a number of "rounds" (or "
76:, who published it in 1962, although it had been used for the
1322:
1098:
899:
Gender and
Computing Algorithms: The case of Stable Matching
323:
A two-dimensional array indexed by an employer and a number
172:
In other words, a matching is stable when there is no pair (
775:
245:
727:"for the theory of stable allocations and the practice of
203:
Animation showing an example of the Gale–Shapley algorithm
145:
of the first matched set which prefers some given element
506:
in the number of participants, it may be considered as
1245:
Gonczarowski, Yannai A.; Friedgut, Ehud (April 2013).
1169:(1981). "Machiavelli and the Gale–Shapley algorithm".
834:
The Stable
Marriage Problem: Structure and Algorithms
516:
469:
433:
396:
370:
349:
329:
277:
257:
183:
The stable matching problem has also been called the
84:(who pointed out its prior application) won the 2012
1244:
149:
of the second matched set over the element to which
1292:"Deferred acceptance and regret-free truth-telling"
1247:"Sisterhood in the Gale–Shapley matching algorithm"
935:"College admissions and the stability of marriage"
538:
491:
455:
418:
376:
355:
335:
283:
263:
576:can prefer each other over their final match. If
1395:
1310:"College admission algorithms in the real world"
1155:
1082:
1011:Bergstrom, Theodore C. (June 1992). "Review of
1161:
1104:
921:
919:
828:
822:
802:Carter, Michael W.; Price, Camille C. (2000).
363:, naming the applicant who is each employer's
1359:
805:Operations Research: A Practical Introduction
628:
925:
916:
801:
795:
663:
107:Stable marriage problem § Applications
101:in the size of the input to the algorithm.
1290:Fernandez, Marcelo Ariel (July 31, 2020).
1238:
1062:. University of Illinois. pp. 170–176
1336:
1289:
1274:
1264:
1010:
895:
880:
725:Nobel Memorial Prize in Economic Sciences
592:after receiving an even better offer, so
549:
1115:
1113:
1050:
1004:
889:
317:such as 0 indicating they are unemployed
246:Implementation details and time analysis
198:
1304:
1298:
1152:See in particular Problem 6, pp. 87–94.
1046:
1044:
1042:
1040:
1015:by A. E. Roth and M. A. O. Sotomayor".
984:
723:Shapley and Roth were awarded the 2012
390:Setting up these data structures takes
27:Procedure for finding a stable matching
14:
1396:
1316:
978:
856:
765:
763:
761:
616:to their final match. In either case,
1353:
1213:
1207:
1119:
1110:
1078:
1076:
850:
1037:
769:
604:stops making offers before reaching
303:of employers with unfilled positions
1252:Electronic Journal of Combinatorics
758:
687:regret-free truth-telling mechanism
88:for work including this algorithm.
80:since the early 1950s. Shapley and
24:
1073:
693:
221:National Resident Matching Program
78:National Resident Matching Program
25:
1425:
1172:The American Mathematical Monthly
1094:. Addison-Wesley. pp. 42–47.
940:The American Mathematical Monthly
896:Giagkousi, Kyriaki (March 2021).
700:university and college admission
668:The Gale–Shapley algorithm is a
554:This algorithm guarantees that:
1283:
1018:Journal of Economic Literature
718:
533:
520:
486:
473:
450:
437:
413:
400:
64:for finding a solution to the
13:
1:
990:"The stable marriage problem"
751:
624:do not form an unstable pair.
600:to their final match. And if
112:
50:deferred acceptance algorithm
1376:10.1126/science.338.6105.314
1105:Gusfield & Irving (1989)
1051:Erickson, Jeff (June 2019).
832:; Irving, Robert W. (1989).
648:among all stable matchings.
502:Although this time bound is
54:propose-and-reject algorithm
7:
741:Deferred-acceptance auction
734:
654:lattice of stable matchings
635:Lattice of stable matchings
194:
10:
1430:
808:. CRC Press. p. 102.
632:
629:Optimality of the solution
608:in their preference list,
163:over the element to which
116:
1347:10.1007/s00453-009-9353-9
860:Social Studies of Science
677:retain the same partner.
1414:Combinatorial algorithms
873:10.1177/0306312708099443
836:. MIT Press. p. 6.
746:Stable roommates problem
664:Strategic considerations
646:worst for all applicants
539:{\displaystyle O(n^{2})}
492:{\displaystyle O(n^{2})}
456:{\displaystyle O(n^{2})}
419:{\displaystyle O(n^{2})}
86:Nobel Prize in Economics
185:stable marriage problem
153:is already matched, and
119:Stable matching problem
66:stable matching problem
789:10.1001/jama.289.7.909
642:best for all employers
565:The matches are stable
550:Correctness guarantees
540:
493:
457:
420:
378:
357:
337:
285:
265:
204:
46:Gale–Shapley algorithm
18:Gale-Shapley algorithm
1053:"4.5 Stable matching"
558:Everyone gets matched
541:
494:
458:
421:
379:
358:
338:
286:
266:
202:
58:Boston Pool algorithm
674:group-strategy proof
514:
467:
431:
394:
368:
347:
327:
275:
255:
141:There is an element
1259:(2): P12:1–P12:18.
1224:10.1007/11841036_39
994:The Brandeis Review
882:20.500.11850/121579
167:is already matched.
127:job applicants and
48:(also known as the
670:truthful mechanism
588:would only reject
580:makes an offer to
536:
489:
453:
416:
374:
353:
333:
306:A one-dimensional
281:
261:
205:
189:marriage proposals
94:truthful mechanism
68:. It is named for
377:{\displaystyle i}
356:{\displaystyle n}
336:{\displaystyle i}
284:{\displaystyle n}
264:{\displaystyle n}
16:(Redirected from
1421:
1388:
1387:
1357:
1351:
1350:
1340:
1320:
1314:
1313:
1302:
1296:
1295:
1287:
1281:
1280:
1278:
1268:
1242:
1236:
1235:
1211:
1205:
1204:
1159:
1153:
1151:
1131:
1121:Knuth, Donald E.
1117:
1108:
1102:
1096:
1095:
1092:Algorithm Design
1080:
1071:
1070:
1068:
1067:
1057:
1048:
1035:
1034:
1008:
1002:
1001:
982:
976:
975:
973:
972:
963:. Archived from
923:
914:
913:
911:
910:
904:
893:
887:
886:
884:
854:
848:
847:
826:
820:
819:
799:
793:
792:
767:
545:
543:
542:
537:
532:
531:
498:
496:
495:
490:
485:
484:
462:
460:
459:
454:
449:
448:
425:
423:
422:
417:
412:
411:
385:
383:
381:
380:
375:
362:
360:
359:
354:
342:
340:
339:
334:
290:
288:
287:
282:
270:
268:
267:
262:
130:
126:
42:computer science
21:
1429:
1428:
1424:
1423:
1422:
1420:
1419:
1418:
1404:Stable matching
1394:
1393:
1392:
1391:
1358:
1354:
1321:
1317:
1306:Mathieu, Claire
1303:
1299:
1288:
1284:
1243:
1239:
1212:
1208:
1185:10.2307/2321753
1167:Freedman, D. A.
1160:
1156:
1140:
1129:
1118:
1111:
1103:
1099:
1081:
1074:
1065:
1063:
1055:
1049:
1038:
1009:
1005:
983:
979:
970:
968:
953:10.2307/2312726
924:
917:
908:
906:
902:
894:
890:
855:
851:
844:
827:
823:
816:
800:
796:
768:
759:
754:
737:
721:
696:
694:Generalizations
666:
637:
631:
552:
527:
523:
515:
512:
511:
480:
476:
468:
465:
464:
444:
440:
432:
429:
428:
407:
403:
395:
392:
391:
369:
366:
365:
364:
348:
345:
344:
328:
325:
324:
293:data structures
276:
273:
272:
256:
253:
252:
248:
197:
170:
128:
124:
121:
115:
28:
23:
22:
15:
12:
11:
5:
1427:
1417:
1416:
1411:
1406:
1390:
1389:
1352:
1331:(1): 102–118.
1315:
1297:
1282:
1237:
1206:
1179:(7): 485–494.
1154:
1138:
1109:
1107:, p. 182.
1097:
1084:Kleinberg, Jon
1072:
1036:
1025:(2): 896–898.
1003:
986:Mairson, Harry
977:
931:Shapley, L. S.
915:
888:
867:(2): 289–308.
849:
842:
821:
814:
794:
783:(7): 909–912.
771:Roth, Alvin E.
756:
755:
753:
750:
749:
748:
743:
736:
733:
720:
717:
695:
692:
665:
662:
633:Main article:
630:
627:
626:
625:
612:cannot prefer
596:cannot prefer
566:
563:
559:
551:
548:
535:
530:
526:
522:
519:
488:
483:
479:
475:
472:
452:
447:
443:
439:
436:
415:
410:
406:
402:
399:
388:
387:
373:
352:
332:
321:
318:
315:sentinel value
311:
304:
280:
260:
247:
244:
243:
242:
239:
235:
196:
193:
169:
168:
154:
138:
117:Main article:
114:
111:
26:
9:
6:
4:
3:
2:
1426:
1415:
1412:
1410:
1409:Lloyd Shapley
1407:
1405:
1402:
1401:
1399:
1385:
1381:
1377:
1373:
1370:(6105): 314.
1369:
1365:
1364:
1356:
1348:
1344:
1339:
1334:
1330:
1326:
1319:
1311:
1307:
1301:
1293:
1286:
1277:
1276:10.37236/3267
1272:
1267:
1262:
1258:
1254:
1253:
1248:
1241:
1233:
1229:
1225:
1221:
1217:
1210:
1202:
1198:
1194:
1190:
1186:
1182:
1178:
1174:
1173:
1168:
1164:
1163:Dubins, L. E.
1158:
1149:
1145:
1141:
1139:0-8405-0342-3
1135:
1128:
1127:
1122:
1116:
1114:
1106:
1101:
1093:
1089:
1085:
1079:
1077:
1061:
1054:
1047:
1045:
1043:
1041:
1032:
1028:
1024:
1020:
1019:
1014:
1007:
999:
995:
991:
987:
981:
967:on 2017-09-25
966:
962:
958:
954:
950:
946:
942:
941:
936:
932:
928:
922:
920:
901:
900:
892:
883:
878:
874:
870:
866:
862:
861:
853:
845:
843:9780262515528
839:
835:
831:
830:Gusfield, Dan
825:
817:
815:9780849322563
811:
807:
806:
798:
790:
786:
782:
778:
777:
772:
766:
764:
762:
757:
747:
744:
742:
739:
738:
732:
730:
729:market design
726:
716:
713:
707:
705:
701:
691:
689:
688:
683:
678:
675:
671:
661:
657:
655:
649:
647:
643:
636:
623:
619:
615:
611:
607:
603:
599:
595:
591:
587:
583:
579:
575:
572:and employer
571:
568:No applicant
567:
564:
560:
557:
556:
555:
547:
528:
524:
517:
509:
505:
500:
481:
477:
470:
445:
441:
434:
408:
404:
397:
371:
350:
330:
322:
319:
316:
312:
309:
305:
302:
298:
297:
296:
294:
278:
258:
240:
236:
233:
232:
231:
229:
224:
222:
218:
217:Alvin E. Roth
214:
213:Lloyd Shapley
210:
201:
192:
190:
186:
181:
179:
175:
166:
162:
159:also prefers
158:
155:
152:
148:
144:
140:
139:
137:
135:
120:
110:
108:
102:
100:
95:
89:
87:
83:
82:Alvin E. Roth
79:
75:
74:Lloyd Shapley
71:
67:
63:
59:
55:
51:
47:
43:
39:
35:
30:
19:
1367:
1361:
1355:
1328:
1325:Algorithmica
1324:
1318:
1300:
1285:
1256:
1250:
1240:
1215:
1209:
1176:
1170:
1157:
1125:
1100:
1091:
1064:. Retrieved
1059:
1022:
1016:
1012:
1006:
997:
993:
980:
969:. Retrieved
965:the original
944:
938:
907:. Retrieved
898:
891:
864:
858:
852:
833:
824:
804:
797:
780:
774:
722:
708:
703:
697:
686:
681:
679:
673:
667:
658:
650:
645:
641:
638:
621:
617:
613:
609:
605:
601:
597:
593:
589:
585:
581:
577:
573:
569:
553:
501:
389:
249:
225:
206:
184:
182:
177:
173:
171:
164:
160:
156:
150:
146:
142:
133:
122:
103:
90:
57:
53:
49:
45:
31:
29:
1088:Tardos, Éva
947:(1): 9–14.
719:Recognition
508:linear time
136:stable if:
34:mathematics
1398:Categories
1066:2023-12-19
1060:Algorithms
971:2019-11-20
909:2023-12-20
752:References
712:Parcoursup
682:truncation
386:preference
343:from 1 to
228:iterations
209:David Gale
113:Background
70:David Gale
1338:0812.4893
1266:1104.2217
504:quadratic
207:In 1962,
62:algorithm
38:economics
1384:23087221
1308:(2018).
1123:(1976).
988:(1992).
933:(1962).
927:Gale, D.
735:See also
271:, where
195:Solution
60:) is an
1363:Science
1232:2347162
1201:0628016
1193:2321753
1148:0488980
1031:2727713
961:2312726
584:, then
1382:
1230:
1199:
1191:
1146:
1136:
1029:
959:
840:
812:
99:linear
44:, the
40:, and
1333:arXiv
1261:arXiv
1189:JSTOR
1130:(PDF)
1056:(PDF)
1027:JSTOR
957:JSTOR
903:(PDF)
704:quota
308:array
56:, or
1380:PMID
1134:ISBN
838:ISBN
810:ISBN
776:JAMA
644:and
620:and
211:and
72:and
1372:doi
1368:338
1343:doi
1271:doi
1220:doi
1181:doi
949:doi
877:hdl
869:doi
785:doi
781:289
301:set
134:not
32:In
1400::
1378:.
1366:.
1341:.
1329:58
1327:.
1269:.
1257:20
1255:.
1249:.
1228:MR
1226:.
1197:MR
1195:.
1187:.
1177:88
1175:.
1165:;
1144:MR
1142:.
1112:^
1086:;
1075:^
1058:.
1039:^
1023:30
1021:.
998:12
996:.
992:.
955:.
945:69
943:.
937:.
929:;
918:^
875:.
865:39
863:.
779:.
760:^
656:.
546:.
499:.
384:th
299:A
295::
223:.
176:,
109:.
52:,
36:,
1386:.
1374::
1349:.
1345::
1335::
1279:.
1273::
1263::
1234:.
1222::
1203:.
1183::
1150:.
1069:.
1033:.
1000:.
974:.
951::
912:.
885:.
879::
871::
846:.
818:.
791:.
787::
622:Y
618:X
614:X
610:Y
606:X
602:Y
598:Y
594:X
590:Y
586:X
582:X
578:Y
574:Y
570:X
534:)
529:2
525:n
521:(
518:O
487:)
482:2
478:n
474:(
471:O
451:)
446:2
442:n
438:(
435:O
414:)
409:2
405:n
401:(
398:O
372:i
351:n
331:i
279:n
259:n
178:B
174:A
165:B
161:A
157:B
151:A
147:B
143:A
129:n
125:n
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.