הפוסט להלן מציג דרך לממש עץ בעזרת מספרים ראשוניים, תוך שימוש בתכונה שכל מספר יכול להיות מיוצג כמכפלה של מספרים ראשוניים (על ידי פירוק לגורמים).
עץ בתורת הגרפים מוגדר כגרף מכוון בו לכל קודקוד יש לכל היותר קודקוד אחד שמחובר אליו בקשת,
והוא יכול לתאר מבנים או תהליכים שונים:
1. מערכת היררכית בארגון בה לכל אחד יש מנהל אליו הוא כפוף (זולת המנהל הבכיר ביותר), אם כי למנהל יכולים להיות כפופים מספר עובדים.
2. מבנה דוח כספי מורכב. למשל- מאזן מחולק לנכסים ולהתחייבויות והון עצמי; ההתחייבויות מחולקות להתחייבויות לזמן קצר ולזמן ארוך; התחייבויות לזמן קצר כוללות לקוחות, שכר עובדים, וכך הלאה.
3. חלוקה של מערכת החי לסוגים, מינים, משפחות וכו'.
4. משחק כדוגמת שחמט בו לשחקן הפותח (הלבן) יש 20 אפשרויות שונות כיצד ללכת, לשחקן השני (השחור) יש מספר תגובות אפשריות לכל צעד של הלבן, וכך הלאה (זהו עץ בעל מימדים אסטרונומיים, אך עדיין- עץ).
5. מערכת מחיצות, מחיצות משנה, וקבצים בדיסק.
פעם שמעתי הצעה להשתמש במונח "אילן" במקום במונח "עץ" כתרגום ל-Tree בתורת הגרפים מכיוון שהמילה עץ כבר יוחדה לחומר עץ (Wood) ולכן לא ראוי להעמיס עליה משמעות נוספת, אך ההצעה לא התקבלה וחבל.
המימוש הטבעי לעץ בדטבייס רלציוני הוא בעזת טבלה המקושרת לעצמה ביחס של 1:N (אחת לרבים): בכל שורה המציינת עובד (בהתייחס לדוגמה 1 הנ"ל) יש עמודת מנהל, ועמודת המפתח מקושרת לעמודה זו שכן למנהל שצויין בה יש שורה משלו בה ניתן למצוא פרטים עליו ועל המנהל שלו עצמו.
מימוש זה נוח מבחינת הזנת נתונים ועדכון עובדים ספציפיים- מציינים לכל עובד מי המנהל שלו, וכשמנהל מתחלף- מעדכנים את עמודת המנהל של כל העובדים שבעמודת המנהל שלהם מופיע הקודם.
החסרון שלו הוא בשליפה חלקים מהעץ: כל העובדים הכפופים במישרין או בעקיפין למנהל מסויים, כל "שרשרת הפיקוד" אליה כפוף עובד מסויים, עדכון שכר במחלקה מסויימת וכו'. פעולות אלו דורשות שימוש ברקורסיה והן עלולות להיות כבדות מאוד בשימוש שוטף.
כתוצאה מכך החלו לחפש פתרונות חלופיים שיאפשרו למצוא בקלות את מקומו של כל קודקוד (=עובד) בעץ וכך לחסוך את השימוש ברקורסיה.
דוגמה לפתרון כזה הוא שימוש בסדרות מקוננות (Nested Sets) כפי שצחי פניגשטיין כתב לאחרונה. בשיטה זו המתבססת על תורת הקבוצות – כל שורה מיוצגת על ידי ערך ימני R וערך שמאלי L המציינים תחום (R<L), שהוא עצמו נמצא בתוך התחום של המנהל של אותה שורה (=עובד). כך קל לאתר את כל העובדים של מנהל מסויים (נמצאים בתוך התחום שלו) או את כל המנהלים של עובד מסויים (הוא נמצא בתחום שלהם), אם כי קביעת התחומים ותחזוקתם לאור שינויים במבנה הארגוני- יוצרים בעיות מורכבות שהיו נפתרות בקלות בשיטה הישנה.
"הווה מחשב שכר מצווה כנגד הפסדה" פסקו חז"ל, וכך גם אנחנו במקרה זה.
פתרון אחר הוא שימוש ב-HierarchyID שקיים החל מגרסה 2008. מדובר בסוג נתון המתבסס על CLR, והוא שומר בתוכו את ההיררכיה שמעל כל עובד (כלומר- המנהלים שלו). סוג נתון זה מגיע עם מערכת מתודות קיימת שמאפשרת בקלות למצוא מי כפוף למי, לבצע שינויים וכו'; ועל כך כתב לאחרונה אסף אביב.
השימוש ב-FileTable החל מגרסת 2012 מתבסס על שימוש ב-HierarchyID, וכפי שציינתי- למערכת המחיצות בדיסק יש מבנה של עץ.
הפוסט להלן מציג פתרון שדומה בגישה שלו לזה של ה-HierarchyID (בכל שורה שמור מידע לגבי "שרשרת הפיקוד" מעליה): לכל שורה בטבלה נתאים מספר ראשוני בעמודה אחת, ונציין את מכפלת המספרים הראשוניים שמעליו בעמודה אחרת. אם נקפיד שכל מספר ראשוני יהיה גדול מזה שמעליו- הפירוק לגורמים של כל מכפלה יחזיר סדרת מספרים ראשוניים שיציינו את המנהלים של אותו עובד מהקטן (המנהל הבכיר) לגדול (המנהל הזוטר הישיר).
למשל- לעובד גרי מצויין בעמודה אחת המספר הראשוני 53, ובעמודה אחרת המכפלה 627=3*11*19 המציינת שהמנהל הישיר של גרי הוא זה שהראשוני שלו 19 והמכפלה שלו 33=3*11, המנהל שמעליו הוא זה שהראשוני שלו 11 והמכפלה שלו 3, והמנהל הבכיר ביותר הוא זה שהראשוני שלו 3 והמכפלה 1 (הערך ההתחלתי).
לכל העובדים הכפופים לגרי תהיה מכפלה 33231=627*53=3*11*19*53, ומספרים ראשוניים גדולים מ-53.
נצטרך להחזיק טבלת מספרים ראשוניים בת 10,000 מספרים שאמורה להספיק לרוב הצרכים המעשיים, ולצידה המגבלה של עמודת המכפלה שהיא מסוג BigInt שיכול להגיע לתשעת אלפים מליוני מליארד בערך..
בדקתי את המערכת שלהלן עם טבלה בת יותר מעשרה מליון שורות, ולא הייתה כל בעייה.
ניצור קודם כל את טבלת המספרים הראשוניים (מטעמי יעילות- נאנדקס אותה רק לאחר שתתמלא):
If Object_Id('T_Primes','U') Is Not Null Drop Table T_Primes;
Go
Declare @S Varchar(Max)='2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,3581,3583,3593,3607,3613,3617,3623,3631,3637,3643,3659,3671,3673,3677,3691,3697,3701,3709,3719,3727,3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,3823,3833,3847,3851,3853,3863,3877,3881,3889,3907,3911,3917,3919,3923,3929,3931,3943,3947,3967,3989,4001,4003,4007,4013,4019,4021,4027,4049,4051,4057,4073,4079,4091,4093,4099,4111,4127,4129,4133,4139,4153,4157,4159,4177,4201,4211,4217,4219,4229,4231,4241,4243,4253,4259,4261,4271,4273,4283,4289,4297,4327,4337,4339,4349,4357,4363,4373,4391,4397,4409,4421,4423,4441,4447,4451,4457,4463,4481,4483,4493,4507,4513,4517,4519,4523,4547,4549,4561,4567,4583,4591,4597,4603,4621,4637,4639,4643,4649,4651,4657,4663,4673,4679,4691,4703,4721,4723,4729,4733,4751,4759,4783,4787,4789,4793,4799,4801,4813,4817,4831,4861,4871,4877,4889,4903,4909,4919,4931,4933,4937,4943,4951,4957,4967,4969,4973,4987,4993,4999,5003,5009,5011,5021,5023,5039,5051,5059,5077,5081,5087,5099,5101,5107,5113,5119,5147,5153,5167,5171,5179,5189,5197,5209,5227,5231,5233,5237,5261,5273,5279,5281,5297,5303,5309,5323,5333,5347,5351,5381,5387,5393,5399,5407,5413,5417,5419,5431,5437,5441,5443,5449,5471,5477,5479,5483,5501,5503,5507,5519,5521,5527,5531,5557,5563,5569,5573,5581,5591,5623,5639,5641,5647,5651,5653,5657,5659,5669,5683,5689,5693,5701,5711,5717,5737,5741,5743,5749,5779,5783,5791,5801,5807,5813,5821,5827,5839,5843,5849,5851,5857,5861,5867,5869,5879,5881,5897,5903,5923,5927,5939,5953,5981,5987,6007,6011,6029,6037,6043,6047,6053,6067,6073,6079,6089,6091,6101,6113,6121,6131,6133,6143,6151,6163,6173,6197,6199,6203,6211,6217,6221,6229,6247,6257,6263,6269,6271,6277,6287,6299,6301,6311,6317,6323,6329,6337,6343,6353,6359,6361,6367,6373,6379,6389,6397,6421,6427,6449,6451,6469,6473,6481,6491,6521,6529,6547,6551,6553,6563,6569,6571,6577,6581,6599,6607,6619,6637,6653,6659,6661,6673,6679,6689,6691,6701,6703,6709,6719,6733,6737,6761,6763,6779,6781,6791,6793,6803,6823,6827,6829,6833,6841,6857,6863,6869,6871,6883,6899,6907,6911,6917,6947,6949,6959,6961,6967,6971,6977,6983,6991,6997,7001,7013,7019,7027,7039,7043,7057,7069,7079,7103,7109,7121,7127,7129,7151,7159,7177,7187,7193,7207,7211,7213,7219,7229,7237,7243,7247,7253,7283,7297,7307,7309,7321,7331,7333,7349,7351,7369,7393,7411,7417,7433,7451,7457,7459,7477,7481,7487,7489,7499,7507,7517,7523,7529,7537,7541,7547,7549,7559,7561,7573,7577,7583,7589,7591,7603,7607,7621,7639,7643,7649,7669,7673,7681,7687,7691,7699,7703,7717,7723,7727,7741,7753,7757,7759,7789,7793,7817,7823,7829,7841,7853,7867,7873,7877,7879,7883,7901,7907,7919,7927,7933,7937,7949,7951,7963,7993,8009,8011,8017,8039,8053,8059,8069,8081,8087,8089,8093,8101,8111,8117,8123,8147,8161,8167,8171,8179,8191,8209,8219,8221,8231,8233,8237,8243,8263,8269,8273,8287,8291,8293,8297,8311,8317,8329,8353,8363,8369,8377,8387,8389,8419,8423,8429,8431,8443,8447,8461,8467,8501,8513,8521,8527,8537,8539,8543,8563,8573,8581,8597,8599,8609,8623,8627,8629,8641,8647,8663,8669,8677,8681,8689,8693,8699,8707,8713,8719,8731,8737,8741,8747,8753,8761,8779,8783,8803,8807,8819,8821,8831,8837,8839,8849,8861,8863,8867,8887,8893,8923,8929,8933,8941,8951,8963,8969,8971,8999,9001,9007,9011,9013,9029,9041,9043,9049,9059,9067,9091,9103,9109,9127,9133,9137,9151,9157,9161,9173,9181,9187,9199,9203,9209,9221,9227,9239,9241,9257,9277,9281,9283,9293,9311,9319,9323,9337,9341,9343,9349,9371,9377,9391,9397,9403,9413,9419,9421,9431,9433,9437,9439,9461,9463,9467,9473,9479,9491,9497,9511,9521,9533,9539,9547,9551,9587,9601,9613,9619,9623,9629,9631,9643,9649,9661,9677,9679,9689,9697,9719,9721,9733,9739,9743,9749,9767,9769,9781,9787,9791,9803,9811,9817,9829,9833,9839,9851,9857,9859,9871,9883,9887,9901,9907,9923,9929,9931,9941,9949,9967,9973,10007,10009,10037,10039,10061,10067,10069,10079,10091,10093,10099,10103,10111,10133,10139,10141,10151,10159,10163,10169,10177,10181,10193,10211,10223,10243,10247,10253,10259,10267,10271,10273,10289,10301,10303,10313,10321,10331,10333,10337,10343,10357,10369,10391,10399,10427,10429,10433,10453,10457,10459,10463,10477,10487,10499,10501,10513,10529,10531,10559,10567,10589,10597,10601,10607,10613,10627,10631,10639,10651,10657,10663,10667,10687,10691,10709,10711,10723,10729,10733,10739,10753,10771,10781,10789,10799,10831,10837,10847,10853,10859,10861,10867,10883,10889,10891,10903,10909,10937,10939,10949,10957,10973,10979,10987,10993,11003,11027,11047,11057,11059,11069,11071,11083,11087,11093,11113,11117,11119,11131,11149,11159,11161,11171,11173,11177,11197,11213,11239,11243,11251,11257,11261,11273,11279,11287,11299,11311,11317,11321,11329,11351,11353,11369,11383,11393,11399,11411,11423,11437,11443,11447,11467,11471,11483,11489,11491,11497,11503,11519,11527,11549,11551,11579,11587,11593,11597,11617,11621,11633,11657,11677,11681,11689,11699,11701,11717,11719,11731,11743,11777,11779,11783,11789,11801,11807,11813,11821,11827,11831,11833,11839,11863,11867,11887,11897,11903,11909,11923,11927,11933,11939,11941,11953,11959,11969,11971,11981,11987,12007,12011,12037,12041,12043,12049,12071,12073,12097,12101,12107,12109,12113,12119,12143,12149,12157,12161,12163,12197,12203,12211,12227,12239,12241,12251,12253,12263,12269,12277,12281,12289,12301,12323,12329,12343,12347,12373,12377,12379,12391,12401,12409,12413,12421,12433,12437,12451,12457,12473,12479,12487,12491,12497,12503,12511,12517,12527,12539,12541,12547,12553,12569,12577,12583,12589,12601,12611,12613,12619,12637,12641,12647,12653,12659,12671,12689,12697,12703,12713,12721,12739,12743,12757,12763,12781,12791,12799,12809,12821,12823,12829,12841,12853,12889,12893,12899,12907,12911,12917,12919,12923,12941,12953,12959,12967,12973,12979,12983,13001,13003,13007,13009,13033,13037,13043,13049,13063,13093,13099,13103,13109,13121,13127,13147,13151,13159,13163,13171,13177,13183,13187,13217,13219,13229,13241,13249,13259,13267,13291,13297,13309,13313,13327,13331,13337,13339,13367,13381,13397,13399,13411,13417,13421,13441,13451,13457,13463,13469,13477,13487,13499,13513,13523,13537,13553,13567,13577,13591,13597,13613,13619,13627,13633,13649,13669,13679,13681,13687,13691,13693,13697,13709,13711,13721,13723,13729,13751,13757,13759,13763,13781,13789,13799,13807,13829,13831,13841,13859,13873,13877,13879,13883,13901,13903,13907,13913,13921,13931,13933,13963,13967,13997,13999,14009,14011,14029,14033,14051,14057,14071,14081,14083,14087,14107,14143,14149,14153,14159,14173,14177,14197,14207,14221,14243,14249,14251,14281,14293,14303,14321,14323,14327,14341,14347,14369,14387,14389,14401,14407,14411,14419,14423,14431,14437,14447,14449,14461,14479,14489,14503,14519,14533,14537,14543,14549,14551,14557,14561,14563,14591,14593,14621,14627,14629,14633,14639,14653,14657,14669,14683,14699,14713,14717,14723,14731,14737,14741,14747,14753,14759,14767,14771,14779,14783,14797,14813,14821,14827,14831,14843,14851,14867,14869,14879,14887,14891,14897,14923,14929,14939,14947,14951,14957,14969,14983,15013,15017,15031,15053,15061,15073,15077,15083,15091,15101,15107,15121,15131,15137,15139,15149,15161,15173,15187,15193,15199,15217,15227,15233,15241,15259,15263,15269,15271,15277,15287,15289,15299,15307,15313,15319,15329,15331,15349,15359,15361,15373,15377,15383,15391,15401,15413,15427,15439,15443,15451,15461,15467,15473,15493,15497,15511,15527,15541,15551,15559,15569,15581,15583,15601,15607,15619,15629,15641,15643,15647,15649,15661,15667,15671,15679,15683,15727,15731,15733,15737,15739,15749,15761,15767,15773,15787,15791,15797,15803,15809,15817,15823,15859,15877,15881,15887,15889,15901,15907,15913,15919,15923,15937,15959,15971,15973,15991,16001,16007,16033,16057,16061,16063,16067,16069,16073,16087,16091,16097,16103,16111,16127,16139,16141,16183,16187,16189,16193,16217,16223,16229,16231,16249,16253,16267,16273,16301,16319,16333,16339,16349,16361,16363,16369,16381,16411,16417,16421,16427,16433,16447,16451,16453,16477,16481,16487,16493,16519,16529,16547,16553,16561,16567,16573,16603,16607,16619,16631,16633,16649,16651,16657,16661,16673,16691,16693,16699,16703,16729,16741,16747,16759,16763,16787,16811,16823,16829,16831,16843,16871,16879,16883,16889,16901,16903,16921,16927,16931,16937,16943,16963,16979,16981,16987,16993,17011,17021,17027,17029,17033,17041,17047,17053,17077,17093,17099,17107,17117,17123,17137,17159,17167,17183,17189,17191,17203,17207,17209,17231,17239,17257,17291,17293,17299,17317,17321,17327,17333,17341,17351,17359,17377,17383,17387,17389,17393,17401,17417,17419,17431,17443,17449,17467,17471,17477,17483,17489,17491,17497,17509,17519,17539,17551,17569,17573,17579,17581,17597,17599,17609,17623,17627,17657,17659,17669,17681,17683,17707,17713,17729,17737,17747,17749,17761,17783,17789,17791,17807,17827,17837,17839,17851,17863,17881,17891,17903,17909,17911,17921,17923,17929,17939,17957,17959,17971,17977,17981,17987,17989,18013,18041,18043,18047,18049,18059,18061,18077,18089,18097,18119,18121,18127,18131,18133,18143,18149,18169,18181,18191,18199,18211,18217,18223,18229,18233,18251,18253,18257,18269,18287,18289,18301,18307,18311,18313,18329,18341,18353,18367,18371,18379,18397,18401,18413,18427,18433,18439,18443,18451,18457,18461,18481,18493,18503,18517,18521,18523,18539,18541,18553,18583,18587,18593,18617,18637,18661,18671,18679,18691,18701,18713,18719,18731,18743,18749,18757,18773,18787,18793,18797,18803,18839,18859,18869,18899,18911,18913,18917,18919,18947,18959,18973,18979,19001,19009,19013,19031,19037,19051,19069,19073,19079,19081,19087,19121,19139,19141,19157,19163,19181,19183,19207,19211,19213,19219,19231,19237,19249,19259,19267,19273,19289,19301,19309,19319,19333,19373,19379,19381,19387,19391,19403,19417,19421,19423,19427,19429,19433,19441,19447,19457,19463,19469,19471,19477,19483,19489,19501,19507,19531,19541,19543,19553,19559,19571,19577,19583,19597,19603,19609,19661,19681,19687,19697,19699,19709,19717,19727,19739,19751,19753,19759,19763,19777,19793,19801,19813,19819,19841,19843,19853,19861,19867,19889,19891,19913,19919,19927,19937,19949,19961,19963,19973,19979,19991,19993,19997,20011,20021,20023,20029,20047,20051,20063,20071,20089,20101,20107,20113,20117,20123,20129,20143,20147,20149,20161,20173,20177,20183,20201,20219,20231,20233,20249,20261,20269,20287,20297,20323,20327,20333,20341,20347,20353,20357,20359,20369,20389,20393,20399,20407,20411,20431,20441,20443,20477,20479,20483,20507,20509,20521,20533,20543,20549,20551,20563,20593,20599,20611,20627,20639,20641,20663,20681,20693,20707,20717,20719,20731,20743,20747,20749,20753,20759,20771,20773,20789,20807,20809,20849,20857,20873,20879,20887,20897,20899,20903,20921,20929,20939,20947,20959,20963,20981,20983,21001,21011,21013,21017,21019,21023,21031,21059,21061,21067,21089,21101,21107,21121,21139,21143,21149,21157,21163,21169,21179,21187,21191,21193,21211,21221,21227,21247,21269,21277,21283,21313,21317,21319,21323,21341,21347,21377,21379,21383,21391,21397,21401,21407,21419,21433,21467,21481,21487,21491,21493,21499,21503,21517,21521,21523,21529,21557,21559,21563,21569,21577,21587,21589,21599,21601,21611,21613,21617,21647,21649,21661,21673,21683,21701,21713,21727,21737,21739,21751,21757,21767,21773,21787,21799,21803,21817,21821,21839,21841,21851,21859,21863,21871,21881,21893,21911,21929,21937,21943,21961,21977,21991,21997,22003,22013,22027,22031,22037,22039,22051,22063,22067,22073,22079,22091,22093,22109,22111,22123,22129,22133,22147,22153,22157,22159,22171,22189,22193,22229,22247,22259,22271,22273,22277,22279,22283,22291,22303,22307,22343,22349,22367,22369,22381,22391,22397,22409,22433,22441,22447,22453,22469,22481,22483,22501,22511,22531,22541,22543,22549,22567,22571,22573,22613,22619,22621,22637,22639,22643,22651,22669,22679,22691,22697,22699,22709,22717,22721,22727,22739,22741,22751,22769,22777,22783,22787,22807,22811,22817,22853,22859,22861,22871,22877,22901,22907,22921,22937,22943,22961,22963,22973,22993,23003,23011,23017,23021,23027,23029,23039,23041,23053,23057,23059,23063,23071,23081,23087,23099,23117,23131,23143,23159,23167,23173,23189,23197,23201,23203,23209,23227,23251,23269,23279,23291,23293,23297,23311,23321,23327,23333,23339,23357,23369,23371,23399,23417,23431,23447,23459,23473,23497,23509,23531,23537,23539,23549,23557,23561,23563,23567,23581,23593,23599,23603,23609,23623,23627,23629,23633,23663,23669,23671,23677,23687,23689,23719,23741,23743,23747,23753,23761,23767,23773,23789,23801,23813,23819,23827,23831,23833,23857,23869,23873,23879,23887,23893,23899,23909,23911,23917,23929,23957,23971,23977,23981,23993,24001,24007,24019,24023,24029,24043,24049,24061,24071,24077,24083,24091,24097,24103,24107,24109,24113,24121,24133,24137,24151,24169,24179,24181,24197,24203,24223,24229,24239,24247,24251,24281,24317,24329,24337,24359,24371,24373,24379,24391,24407,24413,24419,24421,24439,24443,24469,24473,24481,24499,24509,24517,24527,24533,24547,24551,24571,24593,24611,24623,24631,24659,24671,24677,24683,24691,24697,24709,24733,24749,24763,24767,24781,24793,24799,24809,24821,24841,24847,24851,24859,24877,24889,24907,24917,24919,24923,24943,24953,24967,24971,24977,24979,24989,25013,25031,25033,25037,25057,25073,25087,25097,25111,25117,25121,25127,25147,25153,25163,25169,25171,25183,25189,25219,25229,25237,25243,25247,25253,25261,25301,25303,25307,25309,25321,25339,25343,25349,25357,25367,25373,25391,25409,25411,25423,25439,25447,25453,25457,25463,25469,25471,25523,25537,25541,25561,25577,25579,25583,25589,25601,25603,25609,25621,25633,25639,25643,25657,25667,25673,25679,25693,25703,25717,25733,25741,25747,25759,25763,25771,25793,25799,25801,25819,25841,25847,25849,25867,25873,25889,25903,25913,25919,25931,25933,25939,25943,25951,25969,25981,25997,25999,26003,26017,26021,26029,26041,26053,26083,26099,26107,26111,26113,26119,26141,26153,26161,26171,26177,26183,26189,26203,26209,26227,26237,26249,26251,26261,26263,26267,26293,26297,26309,26317,26321,26339,26347,26357,26371,26387,26393,26399,26407,26417,26423,26431,26437,26449,26459,26479,26489,26497,26501,26513,26539,26557,26561,26573,26591,26597,26627,26633,26641,26647,26669,26681,26683,26687,26693,26699,26701,26711,26713,26717,26723,26729,26731,26737,26759,26777,26783,26801,26813,26821,26833,26839,26849,26861,26863,26879,26881,26891,26893,26903,26921,26927,26947,26951,26953,26959,26981,26987,26993,27011,27017,27031,27043,27059,27061,27067,27073,27077,27091,27103,27107,27109,27127,27143,27179,27191,27197,27211,27239,27241,27253,27259,27271,27277,27281,27283,27299,27329,27337,27361,27367,27397,27407,27409,27427,27431,27437,27449,27457,27479,27481,27487,27509,27527,27529,27539,27541,27551,27581,27583,27611,27617,27631,27647,27653,27673,27689,27691,27697,27701,27733,27737,27739,27743,27749,27751,27763,27767,27773,27779,27791,27793,27799,27803,27809,27817,27823,27827,27847,27851,27883,27893,27901,27917,27919,27941,27943,27947,27953,27961,27967,27983,27997,28001,28019,28027,28031,28051,28057,28069,28081,28087,28097,28099,28109,28111,28123,28151,28163,28181,28183,28201,28211,28219,28229,28277,28279,28283,28289,28297,28307,28309,28319,28349,28351,28387,28393,28403,28409,28411,28429,28433,28439,28447,28463,28477,28493,28499,28513,28517,28537,28541,28547,28549,28559,28571,28573,28579,28591,28597,28603,28607,28619,28621,28627,28631,28643,28649,28657,28661,28663,28669,28687,28697,28703,28711,28723,28729,28751,28753,28759,28771,28789,28793,28807,28813,28817,28837,28843,28859,28867,28871,28879,28901,28909,28921,28927,28933,28949,28961,28979,29009,29017,29021,29023,29027,29033,29059,29063,29077,29101,29123,29129,29131,29137,29147,29153,29167,29173,29179,29191,29201,29207,29209,29221,29231,29243,29251,29269,29287,29297,29303,29311,29327,29333,29339,29347,29363,29383,29387,29389,29399,29401,29411,29423,29429,29437,29443,29453,29473,29483,29501,29527,29531,29537,29567,29569,29573,29581,29587,29599,29611,29629,29633,29641,29663,29669,29671,29683,29717,29723,29741,29753,29759,29761,29789,29803,29819,29833,29837,29851,29863,29867,29873,29879,29881,29917,29921,29927,29947,29959,29983,29989,30011,30013,30029,30047,30059,30071,30089,30091,30097,30103,30109,30113,30119,30133,30137,30139,30161,30169,30181,30187,30197,30203,30211,30223,30241,30253,30259,30269,30271,30293,30307,30313,30319,30323,30341,30347,30367,30389,30391,30403,30427,30431,30449,30467,30469,30491,30493,30497,30509,30517,30529,30539,30553,30557,30559,30577,30593,30631,30637,30643,30649,30661,30671,30677,30689,30697,30703,30707,30713,30727,30757,30763,30773,30781,30803,30809,30817,30829,30839,30841,30851,30853,30859,30869,30871,30881,30893,30911,30931,30937,30941,30949,30971,30977,30983,31013,31019,31033,31039,31051,31063,31069,31079,31081,31091,31121,31123,31139,31147,31151,31153,31159,31177,31181,31183,31189,31193,31219,31223,31231,31237,31247,31249,31253,31259,31267,31271,31277,31307,31319,31321,31327,31333,31337,31357,31379,31387,31391,31393,31397,31469,31477,31481,31489,31511,31513,31517,31531,31541,31543,31547,31567,31573,31583,31601,31607,31627,31643,31649,31657,31663,31667,31687,31699,31721,31723,31727,31729,31741,31751,31769,31771,31793,31799,31817,31847,31849,31859,31873,31883,31891,31907,31957,31963,31973,31981,31991,32003,32009,32027,32029,32051,32057,32059,32063,32069,32077,32083,32089,32099,32117,32119,32141,32143,32159,32173,32183,32189,32191,32203,32213,32233,32237,32251,32257,32261,32297,32299,32303,32309,32321,32323,32327,32341,32353,32359,32363,32369,32371,32377,32381,32401,32411,32413,32423,32429,32441,32443,32467,32479,32491,32497,32503,32507,32531,32533,32537,32561,32563,32569,32573,32579,32587,32603,32609,32611,32621,32633,32647,32653,32687,32693,32707,32713,32717,32719,32749,32771,32779,32783,32789,32797,32801,32803,32831,32833,32839,32843,32869,32887,32909,32911,32917,32933,32939,32941,32957,32969,32971,32983,32987,32993,32999,33013,33023,33029,33037,33049,33053,33071,33073,33083,33091,33107,33113,33119,33149,33151,33161,33179,33181,33191,33199,33203,33211,33223,33247,33287,33289,33301,33311,33317,33329,33331,33343,33347,33349,33353,33359,33377,33391,33403,33409,33413,33427,33457,33461,33469,33479,33487,33493,33503,33521,33529,33533,33547,33563,33569,33577,33581,33587,33589,33599,33601,33613,33617,33619,33623,33629,33637,33641,33647,33679,33703,33713,33721,33739,33749,33751,33757,33767,33769,33773,33791,33797,33809,33811,33827,33829,33851,33857,33863,33871,33889,33893,33911,33923,33931,33937,33941,33961,33967,33997,34019,34031,34033,34039,34057,34061,34123,34127,34129,34141,34147,34157,34159,34171,34183,34211,34213,34217,34231,34253,34259,34261,34267,34273,34283,34297,34301,34303,34313,34319,34327,34337,34351,34361,34367,34369,34381,34403,34421,34429,34439,34457,34469,34471,34483,34487,34499,34501,34511,34513,34519,34537,34543,34549,34583,34589,34591,34603,34607,34613,34631,34649,34651,34667,34673,34679,34687,34693,34703,34721,34729,34739,34747,34757,34759,34763,34781,34807,34819,34841,34843,34847,34849,34871,34877,34883,34897,34913,34919,34939,34949,34961,34963,34981,35023,35027,35051,35053,35059,35069,35081,35083,35089,35099,35107,35111,35117,35129,35141,35149,35153,35159,35171,35201,35221,35227,35251,35257,35267,35279,35281,35291,35311,35317,35323,35327,35339,35353,35363,35381,35393,35401,35407,35419,35423,35437,35447,35449,35461,35491,35507,35509,35521,35527,35531,35533,35537,35543,35569,35573,35591,35593,35597,35603,35617,35671,35677,35729,35731,35747,35753,35759,35771,35797,35801,35803,35809,35831,35837,35839,35851,35863,35869,35879,35897,35899,35911,35923,35933,35951,35963,35969,35977,35983,35993,35999,36007,36011,36013,36017,36037,36061,36067,36073,36083,36097,36107,36109,36131,36137,36151,36161,36187,36191,36209,36217,36229,36241,36251,36263,36269,36277,36293,36299,36307,36313,36319,36341,36343,36353,36373,36383,36389,36433,36451,36457,36467,36469,36473,36479,36493,36497,36523,36527,36529,36541,36551,36559,36563,36571,36583,36587,36599,36607,36629,36637,36643,36653,36671,36677,36683,36691,36697,36709,36713,36721,36739,36749,36761,36767,36779,36781,36787,36791,36793,36809,36821,36833,36847,36857,36871,36877,36887,36899,36901,36913,36919,36923,36929,36931,36943,36947,36973,36979,36997,37003,37013,37019,37021,37039,37049,37057,37061,37087,37097,37117,37123,37139,37159,37171,37181,37189,37199,37201,37217,37223,37243,37253,37273,37277,37307,37309,37313,37321,37337,37339,37357,37361,37363,37369,37379,37397,37409,37423,37441,37447,37463,37483,37489,37493,37501,37507,37511,37517,37529,37537,37547,37549,37561,37567,37571,37573,37579,37589,37591,37607,37619,37633,37643,37649,37657,37663,37691,37693,37699,37717,37747,37781,37783,37799,37811,37813,37831,37847,37853,37861,37871,37879,37889,37897,37907,37951,37957,37963,37967,37987,37991,37993,37997,38011,38039,38047,38053,38069,38083,38113,38119,38149,38153,38167,38177,38183,38189,38197,38201,38219,38231,38237,38239,38261,38273,38281,38287,38299,38303,38317,38321,38327,38329,38333,38351,38371,38377,38393,38431,38447,38449,38453,38459,38461,38501,38543,38557,38561,38567,38569,38593,38603,38609,38611,38629,38639,38651,38653,38669,38671,38677,38693,38699,38707,38711,38713,38723,38729,38737,38747,38749,38767,38783,38791,38803,38821,38833,38839,38851,38861,38867,38873,38891,38903,38917,38921,38923,38933,38953,38959,38971,38977,38993,39019,39023,39041,39043,39047,39079,39089,39097,39103,39107,39113,39119,39133,39139,39157,39161,39163,39181,39191,39199,39209,39217,39227,39229,39233,39239,39241,39251,39293,39301,39313,39317,39323,39341,39343,39359,39367,39371,39373,39383,39397,39409,39419,39439,39443,39451,39461,39499,39503,39509,39511,39521,39541,39551,39563,39569,39581,39607,39619,39623,39631,39659,39667,39671,39679,39703,39709,39719,39727,39733,39749,39761,39769,39779,39791,39799,39821,39827,39829,39839,39841,39847,39857,39863,39869,39877,39883,39887,39901,39929,39937,39953,39971,39979,39983,39989,40009,40013,40031,40037,40039,40063,40087,40093,40099,40111,40123,40127,40129,40151,40153,40163,40169,40177,40189,40193,40213,40231,40237,40241,40253,40277,40283,40289,40343,40351,40357,40361,40387,40423,40427,40429,40433,40459,40471,40483,40487,40493,40499,40507,40519,40529,40531,40543,40559,40577,40583,40591,40597,40609,40627,40637,40639,40693,40697,40699,40709,40739,40751,40759,40763,40771,40787,40801,40813,40819,40823,40829,40841,40847,40849,40853,40867,40879,40883,40897,40903,40927,40933,40939,40949,40961,40973,40993,41011,41017,41023,41039,41047,41051,41057,41077,41081,41113,41117,41131,41141,41143,41149,41161,41177,41179,41183,41189,41201,41203,41213,41221,41227,41231,41233,41243,41257,41263,41269,41281,41299,41333,41341,41351,41357,41381,41387,41389,41399,41411,41413,41443,41453,41467,41479,41491,41507,41513,41519,41521,41539,41543,41549,41579,41593,41597,41603,41609,41611,41617,41621,41627,41641,41647,41651,41659,41669,41681,41687,41719,41729,41737,41759,41761,41771,41777,41801,41809,41813,41843,41849,41851,41863,41879,41887,41893,41897,41903,41911,41927,41941,41947,41953,41957,41959,41969,41981,41983,41999,42013,42017,42019,42023,42043,42061,42071,42073,42083,42089,42101,42131,42139,42157,42169,42179,42181,42187,42193,42197,42209,42221,42223,42227,42239,42257,42281,42283,42293,42299,42307,42323,42331,42337,42349,42359,42373,42379,42391,42397,42403,42407,42409,42433,42437,42443,42451,42457,42461,42463,42467,42473,42487,42491,42499,42509,42533,42557,42569,42571,42577,42589,42611,42641,42643,42649,42667,42677,42683,42689,42697,42701,42703,42709,42719,42727,42737,42743,42751,42767,42773,42787,42793,42797,42821,42829,42839,42841,42853,42859,42863,42899,42901,42923,42929,42937,42943,42953,42961,42967,42979,42989,43003,43013,43019,43037,43049,43051,43063,43067,43093,43103,43117,43133,43151,43159,43177,43189,43201,43207,43223,43237,43261,43271,43283,43291,43313,43319,43321,43331,43391,43397,43399,43403,43411,43427,43441,43451,43457,43481,43487,43499,43517,43541,43543,43573,43577,43579,43591,43597,43607,43609,43613,43627,43633,43649,43651,43661,43669,43691,43711,43717,43721,43753,43759,43777,43781,43783,43787,43789,43793,43801,43853,43867,43889,43891,43913,43933,43943,43951,43961,43963,43969,43973,43987,43991,43997,44017,44021,44027,44029,44041,44053,44059,44071,44087,44089,44101,44111,44119,44123,44129,44131,44159,44171,44179,44189,44201,44203,44207,44221,44249,44257,44263,44267,44269,44273,44279,44281,44293,44351,44357,44371,44381,44383,44389,44417,44449,44453,44483,44491,44497,44501,44507,44519,44531,44533,44537,44543,44549,44563,44579,44587,44617,44621,44623,44633,44641,44647,44651,44657,44683,44687,44699,44701,44711,44729,44741,44753,44771,44773,44777,44789,44797,44809,44819,44839,44843,44851,44867,44879,44887,44893,44909,44917,44927,44939,44953,44959,44963,44971,44983,44987,45007,45013,45053,45061,45077,45083,45119,45121,45127,45131,45137,45139,45161,45179,45181,45191,45197,45233,45247,45259,45263,45281,45289,45293,45307,45317,45319,45329,45337,45341,45343,45361,45377,45389,45403,45413,45427,45433,45439,45481,45491,45497,45503,45523,45533,45541,45553,45557,45569,45587,45589,45599,45613,45631,45641,45659,45667,45673,45677,45691,45697,45707,45737,45751,45757,45763,45767,45779,45817,45821,45823,45827,45833,45841,45853,45863,45869,45887,45893,45943,45949,45953,45959,45971,45979,45989,46021,46027,46049,46051,46061,46073,46091,46093,46099,46103,46133,46141,46147,46153,46171,46181,46183,46187,46199,46219,46229,46237,46261,46271,46273,46279,46301,46307,46309,46327,46337,46349,46351,46381,46399,46411,46439,46441,46447,46451,46457,46471,46477,46489,46499,46507,46511,46523,46549,46559,46567,46573,46589,46591,46601,46619,46633,46639,46643,46649,46663,46679,46681,46687,46691,46703,46723,46727,46747,46751,46757,46769,46771,46807,46811,46817,46819,46829,46831,46853,46861,46867,46877,46889,46901,46919,46933,46957,46993,46997,47017,47041,47051,47057,47059,47087,47093,47111,47119,47123,47129,47137,47143,47147,47149,47161,47189,47207,47221,47237,47251,47269,47279,47287,47293,47297,47303,47309,47317,47339,47351,47353,47363,47381,47387,47389,47407,47417,47419,47431,47441,47459,47491,47497,47501,47507,47513,47521,47527,47533,47543,47563,47569,47581,47591,47599,47609,47623,47629,47639,47653,47657,47659,47681,47699,47701,47711,47713,47717,47737,47741,47743,47777,47779,47791,47797,47807,47809,47819,47837,47843,47857,47869,47881,47903,47911,47917,47933,47939,47947,47951,47963,47969,47977,47981,48017,48023,48029,48049,48073,48079,48091,48109,48119,48121,48131,48157,48163,48179,48187,48193,48197,48221,48239,48247,48259,48271,48281,48299,48311,48313,48337,48341,48353,48371,48383,48397,48407,48409,48413,48437,48449,48463,48473,48479,48481,48487,48491,48497,48523,48527,48533,48539,48541,48563,48571,48589,48593,48611,48619,48623,48647,48649,48661,48673,48677,48679,48731,48733,48751,48757,48761,48767,48779,48781,48787,48799,48809,48817,48821,48823,48847,48857,48859,48869,48871,48883,48889,48907,48947,48953,48973,48989,48991,49003,49009,49019,49031,49033,49037,49043,49057,49069,49081,49103,49109,49117,49121,49123,49139,49157,49169,49171,49177,49193,49199,49201,49207,49211,49223,49253,49261,49277,49279,49297,49307,49331,49333,49339,49363,49367,49369,49391,49393,49409,49411,49417,49429,49433,49451,49459,49463,49477,49481,49499,49523,49529,49531,49537,49547,49549,49559,49597,49603,49613,49627,49633,49639,49663,49667,49669,49681,49697,49711,49727,49739,49741,49747,49757,49783,49787,49789,49801,49807,49811,49823,49831,49843,49853,49871,49877,49891,49919,49921,49927,49937,49939,49943,49957,49991,49993,49999,50021,50023,50033,50047,50051,50053,50069,50077,50087,50093,50101,50111,50119,50123,50129,50131,50147,50153,50159,50177,50207,50221,50227,50231,50261,50263,50273,50287,50291,50311,50321,50329,50333,50341,50359,50363,50377,50383,50387,50411,50417,50423,50441,50459,50461,50497,50503,50513,50527,50539,50543,50549,50551,50581,50587,50591,50593,50599,50627,50647,50651,50671,50683,50707,50723,50741,50753,50767,50773,50777,50789,50821,50833,50839,50849,50857,50867,50873,50891,50893,50909,50923,50929,50951,50957,50969,50971,50989,50993,51001,51031,51043,51047,51059,51061,51071,51109,51131,51133,51137,51151,51157,51169,51193,51197,51199,51203,51217,51229,51239,51241,51257,51263,51283,51287,51307,51329,51341,51343,51347,51349,51361,51383,51407,51413,51419,51421,51427,51431,51437,51439,51449,51461,51473,51479,51481,51487,51503,51511,51517,51521,51539,51551,51563,51577,51581,51593,51599,51607,51613,51631,51637,51647,51659,51673,51679,51683,51691,51713,51719,51721,51749,51767,51769,51787,51797,51803,51817,51827,51829,51839,51853,51859,51869,51871,51893,51899,51907,51913,51929,51941,51949,51971,51973,51977,51991,52009,52021,52027,52051,52057,52067,52069,52081,52103,52121,52127,52147,52153,52163,52177,52181,52183,52189,52201,52223,52237,52249,52253,52259,52267,52289,52291,52301,52313,52321,52361,52363,52369,52379,52387,52391,52433,52453,52457,52489,52501,52511,52517,52529,52541,52543,52553,52561,52567,52571,52579,52583,52609,52627,52631,52639,52667,52673,52691,52697,52709,52711,52721,52727,52733,52747,52757,52769,52783,52807,52813,52817,52837,52859,52861,52879,52883,52889,52901,52903,52919,52937,52951,52957,52963,52967,52973,52981,52999,53003,53017,53047,53051,53069,53077,53087,53089,53093,53101,53113,53117,53129,53147,53149,53161,53171,53173,53189,53197,53201,53231,53233,53239,53267,53269,53279,53281,53299,53309,53323,53327,53353,53359,53377,53381,53401,53407,53411,53419,53437,53441,53453,53479,53503,53507,53527,53549,53551,53569,53591,53593,53597,53609,53611,53617,53623,53629,53633,53639,53653,53657,53681,53693,53699,53717,53719,53731,53759,53773,53777,53783,53791,53813,53819,53831,53849,53857,53861,53881,53887,53891,53897,53899,53917,53923,53927,53939,53951,53959,53987,53993,54001,54011,54013,54037,54049,54059,54083,54091,54101,54121,54133,54139,54151,54163,54167,54181,54193,54217,54251,54269,54277,54287,54293,54311,54319,54323,54331,54347,54361,54367,54371,54377,54401,54403,54409,54413,54419,54421,54437,54443,54449,54469,54493,54497,54499,54503,54517,54521,54539,54541,54547,54559,54563,54577,54581,54583,54601,54617,54623,54629,54631,54647,54667,54673,54679,54709,54713,54721,54727,54751,54767,54773,54779,54787,54799,54829,54833,54851,54869,54877,54881,54907,54917,54919,54941,54949,54959,54973,54979,54983,55001,55009,55021,55049,55051,55057,55061,55073,55079,55103,55109,55117,55127,55147,55163,55171,55201,55207,55213,55217,55219,55229,55243,55249,55259,55291,55313,55331,55333,55337,55339,55343,55351,55373,55381,55399,55411,55439,55441,55457,55469,55487,55501,55511,55529,55541,55547,55579,55589,55603,55609,55619,55621,55631,55633,55639,55661,55663,55667,55673,55681,55691,55697,55711,55717,55721,55733,55763,55787,55793,55799,55807,55813,55817,55819,55823,55829,55837,55843,55849,55871,55889,55897,55901,55903,55921,55927,55931,55933,55949,55967,55987,55997,56003,56009,56039,56041,56053,56081,56087,56093,56099,56101,56113,56123,56131,56149,56167,56171,56179,56197,56207,56209,56237,56239,56249,56263,56267,56269,56299,56311,56333,56359,56369,56377,56383,56393,56401,56417,56431,56437,56443,56453,56467,56473,56477,56479,56489,56501,56503,56509,56519,56527,56531,56533,56543,56569,56591,56597,56599,56611,56629,56633,56659,56663,56671,56681,56687,56701,56711,56713,56731,56737,56747,56767,56773,56779,56783,56807,56809,56813,56821,56827,56843,56857,56873,56891,56893,56897,56909,56911,56921,56923,56929,56941,56951,56957,56963,56983,56989,56993,56999,57037,57041,57047,57059,57073,57077,57089,57097,57107,57119,57131,57139,57143,57149,57163,57173,57179,57191,57193,57203,57221,57223,57241,57251,57259,57269,57271,57283,57287,57301,57329,57331,57347,57349,57367,57373,57383,57389,57397,57413,57427,57457,57467,57487,57493,57503,57527,57529,57557,57559,57571,57587,57593,57601,57637,57641,57649,57653,57667,57679,57689,57697,57709,57713,57719,57727,57731,57737,57751,57773,57781,57787,57791,57793,57803,57809,57829,57839,57847,57853,57859,57881,57899,57901,57917,57923,57943,57947,57973,57977,57991,58013,58027,58031,58043,58049,58057,58061,58067,58073,58099,58109,58111,58129,58147,58151,58153,58169,58171,58189,58193,58199,58207,58211,58217,58229,58231,58237,58243,58271,58309,58313,58321,58337,58363,58367,58369,58379,58391,58393,58403,58411,58417,58427,58439,58441,58451,58453,58477,58481,58511,58537,58543,58549,58567,58573,58579,58601,58603,58613,58631,58657,58661,58679,58687,58693,58699,58711,58727,58733,58741,58757,58763,58771,58787,58789,58831,58889,58897,58901,58907,58909,58913,58921,58937,58943,58963,58967,58979,58991,58997,59009,59011,59021,59023,59029,59051,59053,59063,59069,59077,59083,59093,59107,59113,59119,59123,59141,59149,59159,59167,59183,59197,59207,59209,59219,59221,59233,59239,59243,59263,59273,59281,59333,59341,59351,59357,59359,59369,59377,59387,59393,59399,59407,59417,59419,59441,59443,59447,59453,59467,59471,59473,59497,59509,59513,59539,59557,59561,59567,59581,59611,59617,59621,59627,59629,59651,59659,59663,59669,59671,59693,59699,59707,59723,59729,59743,59747,59753,59771,59779,59791,59797,59809,59833,59863,59879,59887,59921,59929,59951,59957,59971,59981,59999,60013,60017,60029,60037,60041,60077,60083,60089,60091,60101,60103,60107,60127,60133,60139,60149,60161,60167,60169,60209,60217,60223,60251,60257,60259,60271,60289,60293,60317,60331,60337,60343,60353,60373,60383,60397,60413,60427,60443,60449,60457,60493,60497,60509,60521,60527,60539,60589,60601,60607,60611,60617,60623,60631,60637,60647,60649,60659,60661,60679,60689,60703,60719,60727,60733,60737,60757,60761,60763,60773,60779,60793,60811,60821,60859,60869,60887,60889,60899,60901,60913,60917,60919,60923,60937,60943,60953,60961,61001,61007,61027,61031,61043,61051,61057,61091,61099,61121,61129,61141,61151,61153,61169,61211,61223,61231,61253,61261,61283,61291,61297,61331,61333,61339,61343,61357,61363,61379,61381,61403,61409,61417,61441,61463,61469,61471,61483,61487,61493,61507,61511,61519,61543,61547,61553,61559,61561,61583,61603,61609,61613,61627,61631,61637,61643,61651,61657,61667,61673,61681,61687,61703,61717,61723,61729,61751,61757,61781,61813,61819,61837,61843,61861,61871,61879,61909,61927,61933,61949,61961,61967,61979,61981,61987,61991,62003,62011,62017,62039,62047,62053,62057,62071,62081,62099,62119,62129,62131,62137,62141,62143,62171,62189,62191,62201,62207,62213,62219,62233,62273,62297,62299,62303,62311,62323,62327,62347,62351,62383,62401,62417,62423,62459,62467,62473,62477,62483,62497,62501,62507,62533,62539,62549,62563,62581,62591,62597,62603,62617,62627,62633,62639,62653,62659,62683,62687,62701,62723,62731,62743,62753,62761,62773,62791,62801,62819,62827,62851,62861,62869,62873,62897,62903,62921,62927,62929,62939,62969,62971,62981,62983,62987,62989,63029,63031,63059,63067,63073,63079,63097,63103,63113,63127,63131,63149,63179,63197,63199,63211,63241,63247,63277,63281,63299,63311,63313,63317,63331,63337,63347,63353,63361,63367,63377,63389,63391,63397,63409,63419,63421,63439,63443,63463,63467,63473,63487,63493,63499,63521,63527,63533,63541,63559,63577,63587,63589,63599,63601,63607,63611,63617,63629,63647,63649,63659,63667,63671,63689,63691,63697,63703,63709,63719,63727,63737,63743,63761,63773,63781,63793,63799,63803,63809,63823,63839,63841,63853,63857,63863,63901,63907,63913,63929,63949,63977,63997,64007,64013,64019,64033,64037,64063,64067,64081,64091,64109,64123,64151,64153,64157,64171,64187,64189,64217,64223,64231,64237,64271,64279,64283,64301,64303,64319,64327,64333,64373,64381,64399,64403,64433,64439,64451,64453,64483,64489,64499,64513,64553,64567,64577,64579,64591,64601,64609,64613,64621,64627,64633,64661,64663,64667,64679,64693,64709,64717,64747,64763,64781,64783,64793,64811,64817,64849,64853,64871,64877,64879,64891,64901,64919,64921,64927,64937,64951,64969,64997,65003,65011,65027,65029,65033,65053,65063,65071,65089,65099,65101,65111,65119,65123,65129,65141,65147,65167,65171,65173,65179,65183,65203,65213,65239,65257,65267,65269,65287,65293,65309,65323,65327,65353,65357,65371,65381,65393,65407,65413,65419,65423,65437,65447,65449,65479,65497,65519,65521,65537,65539,65543,65551,65557,65563,65579,65581,65587,65599,65609,65617,65629,65633,65647,65651,65657,65677,65687,65699,65701,65707,65713,65717,65719,65729,65731,65761,65777,65789,65809,65827,65831,65837,65839,65843,65851,65867,65881,65899,65921,65927,65929,65951,65957,65963,65981,65983,65993,66029,66037,66041,66047,66067,66071,66083,66089,66103,66107,66109,66137,66161,66169,66173,66179,66191,66221,66239,66271,66293,66301,66337,66343,66347,66359,66361,66373,66377,66383,66403,66413,66431,66449,66457,66463,66467,66491,66499,66509,66523,66529,66533,66541,66553,66569,66571,66587,66593,66601,66617,66629,66643,66653,66683,66697,66701,66713,66721,66733,66739,66749,66751,66763,66791,66797,66809,66821,66841,66851,66853,66863,66877,66883,66889,66919,66923,66931,66943,66947,66949,66959,66973,66977,67003,67021,67033,67043,67049,67057,67061,67073,67079,67103,67121,67129,67139,67141,67153,67157,67169,67181,67187,67189,67211,67213,67217,67219,67231,67247,67261,67271,67273,67289,67307,67339,67343,67349,67369,67391,67399,67409,67411,67421,67427,67429,67433,67447,67453,67477,67481,67489,67493,67499,67511,67523,67531,67537,67547,67559,67567,67577,67579,67589,67601,67607,67619,67631,67651,67679,67699,67709,67723,67733,67741,67751,67757,67759,67763,67777,67783,67789,67801,67807,67819,67829,67843,67853,67867,67883,67891,67901,67927,67931,67933,67939,67943,67957,67961,67967,67979,67987,67993,68023,68041,68053,68059,68071,68087,68099,68111,68113,68141,68147,68161,68171,68207,68209,68213,68219,68227,68239,68261,68279,68281,68311,68329,68351,68371,68389,68399,68437,68443,68447,68449,68473,68477,68483,68489,68491,68501,68507,68521,68531,68539,68543,68567,68581,68597,68611,68633,68639,68659,68669,68683,68687,68699,68711,68713,68729,68737,68743,68749,68767,68771,68777,68791,68813,68819,68821,68863,68879,68881,68891,68897,68899,68903,68909,68917,68927,68947,68963,68993,69001,69011,69019,69029,69031,69061,69067,69073,69109,69119,69127,69143,69149,69151,69163,69191,69193,69197,69203,69221,69233,69239,69247,69257,69259,69263,69313,69317,69337,69341,69371,69379,69383,69389,69401,69403,69427,69431,69439,69457,69463,69467,69473,69481,69491,69493,69497,69499,69539,69557,69593,69623,69653,69661,69677,69691,69697,69709,69737,69739,69761,69763,69767,69779,69809,69821,69827,69829,69833,69847,69857,69859,69877,69899,69911,69929,69931,69941,69959,69991,69997,70001,70003,70009,70019,70039,70051,70061,70067,70079,70099,70111,70117,70121,70123,70139,70141,70157,70163,70177,70181,70183,70199,70201,70207,70223,70229,70237,70241,70249,70271,70289,70297,70309,70313,70321,70327,70351,70373,70379,70381,70393,70423,70429,70439,70451,70457,70459,70481,70487,70489,70501,70507,70529,70537,70549,70571,70573,70583,70589,70607,70619,70621,70627,70639,70657,70663,70667,70687,70709,70717,70729,70753,70769,70783,70793,70823,70841,70843,70849,70853,70867,70877,70879,70891,70901,70913,70919,70921,70937,70949,70951,70957,70969,70979,70981,70991,70997,70999,71011,71023,71039,71059,71069,71081,71089,71119,71129,71143,71147,71153,71161,71167,71171,71191,71209,71233,71237,71249,71257,71261,71263,71287,71293,71317,71327,71329,71333,71339,71341,71347,71353,71359,71363,71387,71389,71399,71411,71413,71419,71429,71437,71443,71453,71471,71473,71479,71483,71503,71527,71537,71549,71551,71563,71569,71593,71597,71633,71647,71663,71671,71693,71699,71707,71711,71713,71719,71741,71761,71777,71789,71807,71809,71821,71837,71843,71849,71861,71867,71879,71881,71887,71899,71909,71917,71933,71941,71947,71963,71971,71983,71987,71993,71999,72019,72031,72043,72047,72053,72073,72077,72089,72091,72101,72103,72109,72139,72161,72167,72169,72173,72211,72221,72223,72227,72229,72251,72253,72269,72271,72277,72287,72307,72313,72337,72341,72353,72367,72379,72383,72421,72431,72461,72467,72469,72481,72493,72497,72503,72533,72547,72551,72559,72577,72613,72617,72623,72643,72647,72649,72661,72671,72673,72679,72689,72701,72707,72719,72727,72733,72739,72763,72767,72797,72817,72823,72859,72869,72871,72883,72889,72893,72901,72907,72911,72923,72931,72937,72949,72953,72959,72973,72977,72997,73009,73013,73019,73037,73039,73043,73061,73063,73079,73091,73121,73127,73133,73141,73181,73189,73237,73243,73259,73277,73291,73303,73309,73327,73331,73351,73361,73363,73369,73379,73387,73417,73421,73433,73453,73459,73471,73477,73483,73517,73523,73529,73547,73553,73561,73571,73583,73589,73597,73607,73609,73613,73637,73643,73651,73673,73679,73681,73693,73699,73709,73721,73727,73751,73757,73771,73783,73819,73823,73847,73849,73859,73867,73877,73883,73897,73907,73939,73943,73951,73961,73973,73999,74017,74021,74027,74047,74051,74071,74077,74093,74099,74101,74131,74143,74149,74159,74161,74167,74177,74189,74197,74201,74203,74209,74219,74231,74257,74279,74287,74293,74297,74311,74317,74323,74353,74357,74363,74377,74381,74383,74411,74413,74419,74441,74449,74453,74471,74489,74507,74509,74521,74527,74531,74551,74561,74567,74573,74587,74597,74609,74611,74623,74653,74687,74699,74707,74713,74717,74719,74729,74731,74747,74759,74761,74771,74779,74797,74821,74827,74831,74843,74857,74861,74869,74873,74887,74891,74897,74903,74923,74929,74933,74941,74959,75011,75013,75017,75029,75037,75041,75079,75083,75109,75133,75149,75161,75167,75169,75181,75193,75209,75211,75217,75223,75227,75239,75253,75269,75277,75289,75307,75323,75329,75337,75347,75353,75367,75377,75389,75391,75401,75403,75407,75431,75437,75479,75503,75511,75521,75527,75533,75539,75541,75553,75557,75571,75577,75583,75611,75617,75619,75629,75641,75653,75659,75679,75683,75689,75703,75707,75709,75721,75731,75743,75767,75773,75781,75787,75793,75797,75821,75833,75853,75869,75883,75913,75931,75937,75941,75967,75979,75983,75989,75991,75997,76001,76003,76031,76039,76079,76081,76091,76099,76103,76123,76129,76147,76157,76159,76163,76207,76213,76231,76243,76249,76253,76259,76261,76283,76289,76303,76333,76343,76367,76369,76379,76387,76403,76421,76423,76441,76463,76471,76481,76487,76493,76507,76511,76519,76537,76541,76543,76561,76579,76597,76603,76607,76631,76649,76651,76667,76673,76679,76697,76717,76733,76753,76757,76771,76777,76781,76801,76819,76829,76831,76837,76847,76871,76873,76883,76907,76913,76919,76943,76949,76961,76963,76991,77003,77017,77023,77029,77041,77047,77069,77081,77093,77101,77137,77141,77153,77167,77171,77191,77201,77213,77237,77239,77243,77249,77261,77263,77267,77269,77279,77291,77317,77323,77339,77347,77351,77359,77369,77377,77383,77417,77419,77431,77447,77471,77477,77479,77489,77491,77509,77513,77521,77527,77543,77549,77551,77557,77563,77569,77573,77587,77591,77611,77617,77621,77641,77647,77659,77681,77687,77689,77699,77711,77713,77719,77723,77731,77743,77747,77761,77773,77783,77797,77801,77813,77839,77849,77863,77867,77893,77899,77929,77933,77951,77969,77977,77983,77999,78007,78017,78031,78041,78049,78059,78079,78101,78121,78137,78139,78157,78163,78167,78173,78179,78191,78193,78203,78229,78233,78241,78259,78277,78283,78301,78307,78311,78317,78341,78347,78367,78401,78427,78437,78439,78467,78479,78487,78497,78509,78511,78517,78539,78541,78553,78569,78571,78577,78583,78593,78607,78623,78643,78649,78653,78691,78697,78707,78713,78721,78737,78779,78781,78787,78791,78797,78803,78809,78823,78839,78853,78857,78877,78887,78889,78893,78901,78919,78929,78941,78977,78979,78989,79031,79039,79043,79063,79087,79103,79111,79133,79139,79147,79151,79153,79159,79181,79187,79193,79201,79229,79231,79241,79259,79273,79279,79283,79301,79309,79319,79333,79337,79349,79357,79367,79379,79393,79397,79399,79411,79423,79427,79433,79451,79481,79493,79531,79537,79549,79559,79561,79579,79589,79601,79609,79613,79621,79627,79631,79633,79657,79669,79687,79691,79693,79697,79699,79757,79769,79777,79801,79811,79813,79817,79823,79829,79841,79843,79847,79861,79867,79873,79889,79901,79903,79907,79939,79943,79967,79973,79979,79987,79997,79999,80021,80039,80051,80071,80077,80107,80111,80141,80147,80149,80153,80167,80173,80177,80191,80207,80209,80221,80231,80233,80239,80251,80263,80273,80279,80287,80309,80317,80329,80341,80347,80363,80369,80387,80407,80429,80447,80449,80471,80473,80489,80491,80513,80527,80537,80557,80567,80599,80603,80611,80621,80627,80629,80651,80657,80669,80671,80677,80681,80683,80687,80701,80713,80737,80747,80749,80761,80777,80779,80783,80789,80803,80809,80819,80831,80833,80849,80863,80897,80909,80911,80917,80923,80929,80933,80953,80963,80989,81001,81013,81017,81019,81023,81031,81041,81043,81047,81049,81071,81077,81083,81097,81101,81119,81131,81157,81163,81173,81181,81197,81199,81203,81223,81233,81239,81281,81283,81293,81299,81307,81331,81343,81349,81353,81359,81371,81373,81401,81409,81421,81439,81457,81463,81509,81517,81527,81533,81547,81551,81553,81559,81563,81569,81611,81619,81629,81637,81647,81649,81667,81671,81677,81689,81701,81703,81707,81727,81737,81749,81761,81769,81773,81799,81817,81839,81847,81853,81869,81883,81899,81901,81919,81929,81931,81937,81943,81953,81967,81971,81973,82003,82007,82009,82013,82021,82031,82037,82039,82051,82067,82073,82129,82139,82141,82153,82163,82171,82183,82189,82193,82207,82217,82219,82223,82231,82237,82241,82261,82267,82279,82301,82307,82339,82349,82351,82361,82373,82387,82393,82421,82457,82463,82469,82471,82483,82487,82493,82499,82507,82529,82531,82549,82559,82561,82567,82571,82591,82601,82609,82613,82619,82633,82651,82657,82699,82721,82723,82727,82729,82757,82759,82763,82781,82787,82793,82799,82811,82813,82837,82847,82883,82889,82891,82903,82913,82939,82963,82981,82997,83003,83009,83023,83047,83059,83063,83071,83077,83089,83093,83101,83117,83137,83177,83203,83207,83219,83221,83227,83231,83233,83243,83257,83267,83269,83273,83299,83311,83339,83341,83357,83383,83389,83399,83401,83407,83417,83423,83431,83437,83443,83449,83459,83471,83477,83497,83537,83557,83561,83563,83579,83591,83597,83609,83617,83621,83639,83641,83653,83663,83689,83701,83717,83719,83737,83761,83773,83777,83791,83813,83833,83843,83857,83869,83873,83891,83903,83911,83921,83933,83939,83969,83983,83987,84011,84017,84047,84053,84059,84061,84067,84089,84121,84127,84131,84137,84143,84163,84179,84181,84191,84199,84211,84221,84223,84229,84239,84247,84263,84299,84307,84313,84317,84319,84347,84349,84377,84389,84391,84401,84407,84421,84431,84437,84443,84449,84457,84463,84467,84481,84499,84503,84509,84521,84523,84533,84551,84559,84589,84629,84631,84649,84653,84659,84673,84691,84697,84701,84713,84719,84731,84737,84751,84761,84787,84793,84809,84811,84827,84857,84859,84869,84871,84913,84919,84947,84961,84967,84977,84979,84991,85009,85021,85027,85037,85049,85061,85081,85087,85091,85093,85103,85109,85121,85133,85147,85159,85193,85199,85201,85213,85223,85229,85237,85243,85247,85259,85297,85303,85313,85331,85333,85361,85363,85369,85381,85411,85427,85429,85439,85447,85451,85453,85469,85487,85513,85517,85523,85531,85549,85571,85577,85597,85601,85607,85619,85621,85627,85639,85643,85661,85667,85669,85691,85703,85711,85717,85733,85751,85781,85793,85817,85819,85829,85831,85837,85843,85847,85853,85889,85903,85909,85931,85933,85991,85999,86011,86017,86027,86029,86069,86077,86083,86111,86113,86117,86131,86137,86143,86161,86171,86179,86183,86197,86201,86209,86239,86243,86249,86257,86263,86269,86287,86291,86293,86297,86311,86323,86341,86351,86353,86357,86369,86371,86381,86389,86399,86413,86423,86441,86453,86461,86467,86477,86491,86501,86509,86531,86533,86539,86561,86573,86579,86587,86599,86627,86629,86677,86689,86693,86711,86719,86729,86743,86753,86767,86771,86783,86813,86837,86843,86851,86857,86861,86869,86923,86927,86929,86939,86951,86959,86969,86981,86993,87011,87013,87037,87041,87049,87071,87083,87103,87107,87119,87121,87133,87149,87151,87179,87181,87187,87211,87221,87223,87251,87253,87257,87277,87281,87293,87299,87313,87317,87323,87337,87359,87383,87403,87407,87421,87427,87433,87443,87473,87481,87491,87509,87511,87517,87523,87539,87541,87547,87553,87557,87559,87583,87587,87589,87613,87623,87629,87631,87641,87643,87649,87671,87679,87683,87691,87697,87701,87719,87721,87739,87743,87751,87767,87793,87797,87803,87811,87833,87853,87869,87877,87881,87887,87911,87917,87931,87943,87959,87961,87973,87977,87991,88001,88003,88007,88019,88037,88069,88079,88093,88117,88129,88169,88177,88211,88223,88237,88241,88259,88261,88289,88301,88321,88327,88337,88339,88379,88397,88411,88423,88427,88463,88469,88471,88493,88499,88513,88523,88547,88589,88591,88607,88609,88643,88651,88657,88661,88663,88667,88681,88721,88729,88741,88747,88771,88789,88793,88799,88801,88807,88811,88813,88817,88819,88843,88853,88861,88867,88873,88883,88897,88903,88919,88937,88951,88969,88993,88997,89003,89009,89017,89021,89041,89051,89057,89069,89071,89083,89087,89101,89107,89113,89119,89123,89137,89153,89189,89203,89209,89213,89227,89231,89237,89261,89269,89273,89293,89303,89317,89329,89363,89371,89381,89387,89393,89399,89413,89417,89431,89443,89449,89459,89477,89491,89501,89513,89519,89521,89527,89533,89561,89563,89567,89591,89597,89599,89603,89611,89627,89633,89653,89657,89659,89669,89671,89681,89689,89753,89759,89767,89779,89783,89797,89809,89819,89821,89833,89839,89849,89867,89891,89897,89899,89909,89917,89923,89939,89959,89963,89977,89983,89989,90001,90007,90011,90017,90019,90023,90031,90053,90059,90067,90071,90073,90089,90107,90121,90127,90149,90163,90173,90187,90191,90197,90199,90203,90217,90227,90239,90247,90263,90271,90281,90289,90313,90353,90359,90371,90373,90379,90397,90401,90403,90407,90437,90439,90469,90473,90481,90499,90511,90523,90527,90529,90533,90547,90583,90599,90617,90619,90631,90641,90647,90659,90677,90679,90697,90703,90709,90731,90749,90787,90793,90803,90821,90823,90833,90841,90847,90863,90887,90901,90907,90911,90917,90931,90947,90971,90977,90989,90997,91009,91019,91033,91079,91081,91097,91099,91121,91127,91129,91139,91141,91151,91153,91159,91163,91183,91193,91199,91229,91237,91243,91249,91253,91283,91291,91297,91303,91309,91331,91367,91369,91373,91381,91387,91393,91397,91411,91423,91433,91453,91457,91459,91463,91493,91499,91513,91529,91541,91571,91573,91577,91583,91591,91621,91631,91639,91673,91691,91703,91711,91733,91753,91757,91771,91781,91801,91807,91811,91813,91823,91837,91841,91867,91873,91909,91921,91939,91943,91951,91957,91961,91967,91969,91997,92003,92009,92033,92041,92051,92077,92083,92107,92111,92119,92143,92153,92173,92177,92179,92189,92203,92219,92221,92227,92233,92237,92243,92251,92269,92297,92311,92317,92333,92347,92353,92357,92363,92369,92377,92381,92383,92387,92399,92401,92413,92419,92431,92459,92461,92467,92479,92489,92503,92507,92551,92557,92567,92569,92581,92593,92623,92627,92639,92641,92647,92657,92669,92671,92681,92683,92693,92699,92707,92717,92723,92737,92753,92761,92767,92779,92789,92791,92801,92809,92821,92831,92849,92857,92861,92863,92867,92893,92899,92921,92927,92941,92951,92957,92959,92987,92993,93001,93047,93053,93059,93077,93083,93089,93097,93103,93113,93131,93133,93139,93151,93169,93179,93187,93199,93229,93239,93241,93251,93253,93257,93263,93281,93283,93287,93307,93319,93323,93329,93337,93371,93377,93383,93407,93419,93427,93463,93479,93481,93487,93491,93493,93497,93503,93523,93529,93553,93557,93559,93563,93581,93601,93607,93629,93637,93683,93701,93703,93719,93739,93761,93763,93787,93809,93811,93827,93851,93871,93887,93889,93893,93901,93911,93913,93923,93937,93941,93949,93967,93971,93979,93983,93997,94007,94009,94033,94049,94057,94063,94079,94099,94109,94111,94117,94121,94151,94153,94169,94201,94207,94219,94229,94253,94261,94273,94291,94307,94309,94321,94327,94331,94343,94349,94351,94379,94397,94399,94421,94427,94433,94439,94441,94447,94463,94477,94483,94513,94529,94531,94541,94543,94547,94559,94561,94573,94583,94597,94603,94613,94621,94649,94651,94687,94693,94709,94723,94727,94747,94771,94777,94781,94789,94793,94811,94819,94823,94837,94841,94847,94849,94873,94889,94903,94907,94933,94949,94951,94961,94993,94999,95003,95009,95021,95027,95063,95071,95083,95087,95089,95093,95101,95107,95111,95131,95143,95153,95177,95189,95191,95203,95213,95219,95231,95233,95239,95257,95261,95267,95273,95279,95287,95311,95317,95327,95339,95369,95383,95393,95401,95413,95419,95429,95441,95443,95461,95467,95471,95479,95483,95507,95527,95531,95539,95549,95561,95569,95581,95597,95603,95617,95621,95629,95633,95651,95701,95707,95713,95717,95723,95731,95737,95747,95773,95783,95789,95791,95801,95803,95813,95819,95857,95869,95873,95881,95891,95911,95917,95923,95929,95947,95957,95959,95971,95987,95989,96001,96013,96017,96043,96053,96059,96079,96097,96137,96149,96157,96167,96179,96181,96199,96211,96221,96223,96233,96259,96263,96269,96281,96289,96293,96323,96329,96331,96337,96353,96377,96401,96419,96431,96443,96451,96457,96461,96469,96479,96487,96493,96497,96517,96527,96553,96557,96581,96587,96589,96601,96643,96661,96667,96671,96697,96703,96731,96737,96739,96749,96757,96763,96769,96779,96787,96797,96799,96821,96823,96827,96847,96851,96857,96893,96907,96911,96931,96953,96959,96973,96979,96989,96997,97001,97003,97007,97021,97039,97073,97081,97103,97117,97127,97151,97157,97159,97169,97171,97177,97187,97213,97231,97241,97259,97283,97301,97303,97327,97367,97369,97373,97379,97381,97387,97397,97423,97429,97441,97453,97459,97463,97499,97501,97511,97523,97547,97549,97553,97561,97571,97577,97579,97583,97607,97609,97613,97649,97651,97673,97687,97711,97729,97771,97777,97787,97789,97813,97829,97841,97843,97847,97849,97859,97861,97871,97879,97883,97919,97927,97931,97943,97961,97967,97973,97987,98009,98011,98017,98041,98047,98057,98081,98101,98123,98129,98143,98179,98207,98213,98221,98227,98251,98257,98269,98297,98299,98317,98321,98323,98327,98347,98369,98377,98387,98389,98407,98411,98419,98429,98443,98453,98459,98467,98473,98479,98491,98507,98519,98533,98543,98561,98563,98573,98597,98621,98627,98639,98641,98663,98669,98689,98711,98713,98717,98729,98731,98737,98773,98779,98801,98807,98809,98837,98849,98867,98869,98873,98887,98893,98897,98899,98909,98911,98927,98929,98939,98947,98953,98963,98981,98993,98999,99013,99017,99023,99041,99053,99079,99083,99089,99103,99109,99119,99131,99133,99137,99139,99149,99173,99181,99191,99223,99233,99241,99251,99257,99259,99277,99289,99317,99347,99349,99367,99371,99377,99391,99397,99401,99409,99431,99439,99469,99487,99497,99523,99527,99529,99551,99559,99563,99571,99577,99581,99607,99611,99623,99643,99661,99667,99679,99689,99707,99709,99713,99719,99721,99733,99761,99767,99787,99793,99809,99817,99823,99829,99833,99839,99859,99871,99877,99881,99901,99907,99923,99929,99961,99971,99989,99991,100003,100019,100043,100049,100057,100069,100103,100109,100129,100151,100153,100169,100183,100189,100193,100207,100213,100237,100267,100271,100279,100291,100297,100313,100333,100343,100357,100361,100363,100379,100391,100393,100403,100411,100417,100447,100459,100469,100483,100493,100501,100511,100517,100519,100523,100537,100547,100549,100559,100591,100609,100613,100621,100649,100669,100673,100693,100699,100703,100733,100741,100747,100769,100787,100799,100801,100811,100823,100829,100847,100853,100907,100913,100927,100931,100937,100943,100957,100981,100987,100999,101009,101021,101027,101051,101063,101081,101089,101107,101111,101113,101117,101119,101141,101149,101159,101161,101173,101183,101197,101203,101207,101209,101221,101267,101273,101279,101281,101287,101293,101323,101333,101341,101347,101359,101363,101377,101383,101399,101411,101419,101429,101449,101467,101477,101483,101489,101501,101503,101513,101527,101531,101533,101537,101561,101573,101581,101599,101603,101611,101627,101641,101653,101663,101681,101693,101701,101719,101723,101737,101741,101747,101749,101771,101789,101797,101807,101833,101837,101839,101863,101869,101873,101879,101891,101917,101921,101929,101939,101957,101963,101977,101987,101999,102001,102013,102019,102023,102031,102043,102059,102061,102071,102077,102079,102101,102103,102107,102121,102139,102149,102161,102181,102191,102197,102199,102203,102217,102229,102233,102241,102251,102253,102259,102293,102299,102301,102317,102329,102337,102359,102367,102397,102407,102409,102433,102437,102451,102461,102481,102497,102499,102503,102523,102533,102539,102547,102551,102559,102563,102587,102593,102607,102611,102643,102647,102653,102667,102673,102677,102679,102701,102761,102763,102769,102793,102797,102811,102829,102841,102859,102871,102877,102881,102911,102913,102929,102931,102953,102967,102983,103001,103007,103043,103049,103067,103069,103079,103087,103091,103093,103099,103123,103141,103171,103177,103183,103217,103231,103237,103289,103291,103307,103319,103333,103349,103357,103387,103391,103393,103399,103409,103421,103423,103451,103457,103471,103483,103511,103529,103549,103553,103561,103567,103573,103577,103583,103591,103613,103619,103643,103651,103657,103669,103681,103687,103699,103703,103723,103769,103787,103801,103811,103813,103837,103841,103843,103867,103889,103903,103913,103919,103951,103963,103967,103969,103979,103981,103991,103993,103997,104003,104009,104021,104033,104047,104053,104059,104087,104089,104107,104113,104119,104123,104147,104149,104161,104173,104179,104183,104207,104231,104233,104239,104243,104281,104287,104297,104309,104311,104323,104327,104347,104369,104381,104383,104393,104399,104417,104459,104471,104473,104479,104491,104513,104527,104537,104543,104549,104551,104561,104579,104593,104597,104623,104639,104651,104659,104677,104681,104683,104693,104701,104707,104711,104717,104723,104729',
@Delimiter Char(1)=',';
Declare @XML XML=N'<root><r>'+Replace(@S,@Delimiter,'</r><r>')+'</r></root>';
Select Cast(R.value('.','Varchar(Max)') As Int) N
Into T_Primes
From @XML.nodes('//root/r') Records(R);
Go
Alter Table T_Primes Add ID Int Identity Not Null;
Alter Table T_Primes Alter Column N Int Not Null;
Go
Alter Table T_Primes Add Constraint [PK_T_Primes] Primary Key Clustered(N);
Create Unique Index [Idx_T_Primes_ID] On T_Primes(ID);
GO
Select *
From T_Primes;
על ביצוע Split בעזרת XML כתבתי כאן.
וכעת ניצור טבלה לדוגמה ונאכלס אותה בנתונים:
If Object_Id('T_Tree','U') Is Not Null Drop Table T_Tree;
Go
Create Table T_Tree(ID Int Identity,
Prime Int Not Null,
Multiply BigInt Not Null,
[Description] Varchar(Max),
[Level] Int);
Go
Insert
Into T_Tree
Select Top 10 N Prime,
1 Multiply,
Cast(@@Identity As Varchar)+'('+Cast(N As Varchar)+')' [Description],
1 [Level]
From T_Primes
Order By ID;
Go
Update T_Tree Set [Description]=Cast(ID As Varchar)+'('+Cast(Prime As Varchar)+')' Where [Level]=1;
Go
Declare @I Int;
Set @I=2;
While @I<=5
Begin
Print @I;
Insert
Into T_Tree
Select P.N,
Tr.Prime*Tr.Multiply,
[Description],
@I [Level]
From T_Tree Tr
Cross Apply (Select Top 10 *
From T_Primes P
Where P.N>Tr.Prime
Order By ID) P
Where Tr.[Level]=@I-1;
Update T_Tree Set [Description]=IsNull([Description]+',','')+Cast(ID As Varchar)+'('+Cast(Prime As Varchar)+')' Where [Level]=@I;
Set @I=@I+1;
End;
Go
Alter Table T_Tree
Add Constraint PK_T_Tree
Primary Key Clustered (Prime, Multiply);
Go
Create NonClustered Index Idx_T_Tree_ID ON T_Tree(ID);
Go
Select *
From T_Tree;
Go
עמודת Description כוללת מידע על הדרך עד לאותו קודקוד, ו-Level על הרמה שלו (שורש = 1). זהו מידע עזר בלבד לצורך ההדגמה, והמידע הדרוש לתפעול המודל יגזר מעמודות Prime ו-Multiply כאמור.
הנתונים כוללים 10 עצים נפרדים, שבכל אחד 5 רמות ולכל מנהל 10 בנים ישירים, ובסה"כ מעל 100,000 שורות.
למשל- את הדרך מקודקוד נתון עד לקודקוד העליון נשלוף כך:
--העץ המתכנס
Declare @ID Int=5555;
Select Tr1.*
From T_Tree Tr1
Cross Join T_Tree Tr2
Where Tr2.ID=@ID
And Tr2.Multiply%(Tr1.Prime*Tr1.Multiply)=0
And Tr1.Prime<=Tr2.Prime
And Not Exists (Select 1
From T_Primes P
Where Tr2.Multiply%P.N=0
And Tr1.Multiply%P.N>0
And P.N<Tr1.Prime);
השליפה מחפשת שורות שהמכפלה הנוכחית מתחלקת בהן (במכפלת עמודת הראשוני בעמודת המכפלה) ושהמנה אינה כוללת גורמים נוספים באמצע. כלומר- עבור ID=5555 שהמכפלה שלו 14993 מתקבלת מ-11*29*47 של שלושת קודמיו, לא נמנה עבורו את השורה בה המכפלה 11 והראשוני 47 כי 29 חסר באמצע, ובוודאי שלא שורות שבמכפלה או בראשוני שלהם יש ראשוני שהמכפלה 14993 אינה מתחלקת בהם.
הערה מתימטית שכדאי להוסיף- אלגוריתם ההצפנה RSA מבוסס על כך שלכפול שני מספרים ראשוניים זו משימה קלה יחסית למשימת פירוק המכפלה לגורמים (מפתח ההצפנה הפומבי מתבסס על מכפלה של שני ראשוניים, אבל רק מי שמכיר את הגורמים שלה- יוכל לפענח את הצופן), ואפשר לתהות אם אנו לא הולכים להסתבך בנקודה זו.. נכון, אלא שאלגוריתם RSA מתבסס על מכפלה של ראשוניים בני כמה עשרות ספרות, ואילו כאן מדובר בראשונים קטנים יחסית כאשר הגורמים האפשריים שלהם נשלפים מטבלה צנועה בגודלה ומאונדקסת. מדובר לדעתי בעומס לא גדול על ה-CPU.
מה עם הבעייה ההפוכה- העץ המתפרס מקודקוד מסויים (כלומר- כל העובדים הכפופים למנהל)?
--העץ המתפרס
Declare @ID Int=555;
Select Tr2.*
From T_Tree Tr1
Cross Join T_Tree Tr2
Where Tr1.ID=@ID
And Tr2.Multiply%(Tr1.Prime*Tr1.Multiply)=0
And Tr1.Prime<=Tr2.Prime
And Not Exists (Select 1
From T_Primes P
Where Tr2.Multiply%P.N=0
And Tr1.Multiply%P.N>0
And P.N<Tr1.Prime)
Order By Tr2.Prime;
די דומה לשליפה הקודמת, עם השינוי המתבקש בתנאי.
את הפרטים של שורת השורש ניתן למצוא ב-Tr1 שאינו מוצג בשליפה, אבל אם לא נסתפק בזה ונרצה שגם היא תהיה חלק מהסט- אזי:
-- העץ המתפרס כולל השורש
Declare @ID Int=555;
Select Tr2.*
From T_Tree Tr1
Cross Join T_Tree Tr2
Where Tr1.ID=@ID
And (Tr2.Multiply%(Tr1.Prime*Tr1.Multiply)=0 Or Tr2.ID=Tr1.ID)
And Tr1.Prime<=Tr2.Prime
And Not Exists (Select 1
From T_Primes P
Where Tr2.Multiply%P.N=0
And Tr1.Multiply%P.N>0
And P.N<Tr1.Prime)
Order By Tr2.ID;
כיצד מוצאים את "הנכדים" של קודקוד נתון- שתי רמות ממנו?
(אני מזכיר- עמודת Level קיימת רק לצורך בקרה של ההדגמה ואינני עושה בה שימוש)
--העץ המתפרס שתי רמות מעל - הנכדים של
Declare @ID Int=555,
@Lvl Int=2;
Select Tr2.*
From T_Tree Tr1
Cross Join T_Tree Tr2
Where Tr1.ID=@ID
And Tr2.Multiply%(Tr1.Prime*Tr1.Multiply)=0
And Tr1.Prime<=Tr2.Prime
And Not Exists (Select 1
From T_Primes P
Where Tr2.Multiply%P.N=0
And Tr1.Multiply%P.N>0
And P.N<Tr1.Prime)
And (Select Count(*)
From T_Primes P
Where (Tr2.Multiply/Tr1.Multiply)%P.N=0)=@Lvl
Order By Tr2.Prime;
השליפה מוצאת את כל הצאצאים של הקודקוד, ומפעילה תנאי נוסף- מנת המכפלות צריכה להתחלק בשני ראשונים מהטבלה (כי מדובר בשתי רמות).
אם רוצים למחוק את כל תת העץ הנ"ל אזי כך (אני פותח טרנזקציה ומבטל אותה כדי לא למחוק באמת אלא רק להמחיש שזה אפשרי):
--מחיקה של ענף ע"פ הנ"ל
Declare @ID Int=555;
Begin Tran
Delete Tr
From T_Tree Tr
Where ID In (Select Tr2.ID
From T_Tree Tr1
Cross Join T_Tree Tr2
Where Tr1.ID=@ID
And (Tr2.Multiply%(Tr1.Prime*Tr1.Multiply)=0 Or Tr2.ID=Tr1.ID)
And Tr1.Prime<=Tr2.Prime
And Not Exists (Select 1
From T_Primes P
Where Tr2.Multiply%P.N=0
And Tr1.Multiply%P.N>0
And P.N<Tr1.Prime));
RollBack;
את האב של עובד כלשהו ניתן למצוא כך:
--אב
Declare @ID Int=55555;
Select Top 1 Tr1.*
From T_Tree Tr1
Cross Join T_Tree Tr2
Where Tr2.ID=@ID
And Tr2.Multiply=Tr1.Prime*Tr1.Multiply;
ולסיום- "בן הזקונים", כלומר- הבן האחרון, זה עם הראשוני הכי גדול, כך-
--בן הזקונים
Declare @ID Int=555;
Select Top 1 Tr2.*
From T_Tree Tr1
Cross Join T_Tree Tr2
Where Tr1.ID=@ID
And Tr2.Multiply=Tr1.Prime*Tr1.Multiply
Order By Prime Desc;
השאילתה הזו תשמש אותנו בהמשך כשננסה להעביר ענף שלם ממקום למקום, ונצטרך למצוא לו מקום מתאים אחרי בן הזקונים בקודקוד היעד.
הוספת בנים לקודקוד:
--הוספת שורות
Declare @ID Int=555;
Select P.N,
Tr1.Prime*Tr1.Multiply Multiply,
Tr1.[Description]+','+Cast(@@Identity As Varchar)+'('+Cast(P.N As Varchar)+')' [Description],
Tr1.[Level]+1 [Level],
P.Mispar
From T_Tree Tr1
Outer Apply (Select Max(Prime) Prime
From T_Tree Tr2
Where Tr2.Multiply=Tr1.Prime*Tr1.Multiply) Tr2
Outer Apply (Select N,
Row_Number() Over(Order By P.N) Mispar
From T_Primes P
Where Tr2.Prime<P.N) P
Where Tr1.ID=@ID;
זו אינה פקודת Insert אלא Select. יש לעשות Join בינה לבין נתוני המקור לפי עמודת Mispar, להוסיף כמה בנים שצריך, ולזה לבצע Insert לטבלת T_Tree.
ולבסוף- העברת ענף. הפרוצדורה הבאה מקבלת שני פרמטרים- הקודקוד שאת הענף המתחיל ממנו (כולל אתו עצמו) יש להעביר, והקודקוד שיהיה האב החדש שלו (למשל- מינוי מנהל חדש למחלקה):
--העברת ענף
If Object_Id('P_Move','P') Is Not Null Drop Proc P_Move;
Go
Create Proc P_Move @From Int,
@To Int=Null
As
--P_Move 1,777
Declare @PrimeFrom Int,
@PrimeTo Int,
@PrimeFromID Int,
@PrimeToID Int,
@MultiplyFrom BigInt,
@MultiplyTo BigInt,
@MaxPrimeFrom Int;
--הקודקוד שיש להעביר- המכפלה והראשוני שלו, ומקומו הסידורי של הראשוני בטבלת הראשוניים
Select @PrimeFrom=Tr.Prime,
@PrimeFromID=P.ID,
@MultiplyFrom=Multiply
From T_Tree Tr
Inner Join T_Primes P
On Tr.Prime=P.N
Where Tr.ID=@From;
--הקודקוד שאליו יש לשרשר- המכפלה והראשוני שלו, ומקומו הסידורי של הראשוני בטבלת הראשונים
If @To Is Not Null
Select Top 1 @PrimeTo=Tr2.Prime,
@PrimeToID=P.ID,
@MultiplyTo=Tr2.Multiply
From T_Tree Tr1
Cross Join T_Tree Tr2
Inner Join T_Primes P
On Tr2.Prime=P.N
Where Tr1.ID=@To
And Tr2.Multiply=Tr1.Prime*Tr1.Multiply
Order By Tr2.Prime Desc;
Else --אם היעד לא נתון- הענף הופך לעץ עצמאי ליד העצים העצמאיים שכבר קיימים
Select @PrimeTo=Min(N),
@PrimeToID=Min(ID),
@MultiplyTo=1
From T_Primes
Where N>IsNull((Select Max(Prime) Prime
From T_Tree
Where Multiply=1),0);
--הראשוני הכי גדול בענף שמעבירים - יקל על הפירוק לגורמים בהמשך
Select @MaxPrimeFrom=Max(Tr2.Prime)
From T_Tree Tr1
Cross Join T_Tree Tr2
Where Tr1.ID=@From
And Tr2.Multiply%(Tr1.Prime*Tr1.Multiply)=0
And Tr1.Prime<=Tr2.Prime
And Not Exists (Select 1
From T_Primes P
Where Tr2.Multiply%P.N=0
And Tr1.Multiply%P.N>0
And P.N<Tr1.Prime);
--ערכי המשתנים שהוכנו לקראת ההעברה עצמה
Select @PrimeFrom [@PrimeFrom],
@PrimeFromID [@PrimeFromID],
@PrimeTo [@PrimeTo],
@PrimeToID [@PrimeToID],
@MultiplyTo [@MultiplyTo],
@MultiplyFrom [@MultiplyFrom],
@MaxPrimeFrom [@MaxPrimeFrom];
--כל הראשונים ישתנו בהתאם לפער הראשונים בין המקור ליעד והמכפלה תתעדכן בהתאם
With T As
(Select Tr2.*
From T_Tree Tr1
Cross Join T_Tree Tr2
Where Tr1.ID=@From
And (Tr2.Multiply%(Tr1.Prime*Tr1.Multiply)=0 Or Tr2.ID=Tr1.ID)
And Tr1.Prime<=Tr2.Prime
And Not Exists (Select 1
From T_Primes P
Where Tr2.Multiply%P.N=0
And Tr1.Multiply%P.N>0
And P.N<Tr1.Prime))
Update T
Set Prime=P.PrimeHadash,
Multiply=Round(T.Multiply*P.SmLg/@MultiplyFrom*@MultiplyTo,0)
Output 'Deleted' Type,Deleted.*,'Inserted' Type,Inserted.* --השורות שהשתנו- לפני ואחרי השינוי
From T
Cross Apply (Select IsNull(Exp(Sum(Log(P2.N)-Log(P1.N))-Log(Max(P2.N))+Log(Max(P1.N))),1) SmLg,
Max(P1.N) PrimeYashan,
Max(P2.N) PrimeHadash
From T_Primes P1
Inner Join T_Primes P2
On P1.ID=P2.ID+@PrimeFromID-@PrimeToID-1
Where P1.N Between @PrimeFrom And @MaxPrimeFrom
And (T.Multiply%P1.N=0
Or T.Prime=P1.N)) P;
Go
הרעיון באופן כללי- נניח שהראשוני של קודקוד המקור הוא 7 (כלומר- ראשוני מספר 4 בטבלת הראשוניים),
ולקודקוד היעד יש כבר 2 בנים עם הראשוניים 7,11 (כלומר- מספרים 4 ו-5 בטבלת הראשוניים).
זה אומר שאת ראשוני המקור יש "להקפיץ" שני מקומות קדימה מ-7 (מקום 4) ל-13 (מקום 6),
וכך את כל שאר הראשוניים בענף (שני מקומות קדימה).
את המכפלות של כולם יש לחשב מחדש- מוצאים לכל אחד את הגורמים, ומחשבים את המכפלה שלהם בעזרת לוגריתמים (כתבתי על זה כאן בחצי השני המתייחס למדד המחירים לצרכן).
אני מזכיר שוב שעמודות Description ו-Level נועדו רק לצורך הבנת ההדגמה, אינני עושה בהן שימוש, והפרוצדורה הנ"ל אינה מעדכנת אותן.
בנוסף כדאי לציין שאם מעבירים ענף ממקום X למקום Y בעזרת הפרוצדורה, ולאחר מכן מעבירים בחזרה למקור; יש לשים לב לשתי נקודות:
1. לא סתם מחליפים את הפרמטרים במקומותיהם! יש לבדוק קודם לאיזה קודקוד הענף משורשר כרגע (בפרוצדורה מציינים את הקודקוד שהחל ממנו מעבירים ולא את זה אליו הוא משורשר); ורק אז להעביר אותו לקודקוד היעד ואחר כך לקודקוד המקור (הקודקוד שמעבירים הוא אותו אחד בשני המקרים. למשל-
Exec P_Move 560, 777;
Go
Exec P_Move 560, 55;
Go
2. כשהענף מועבר – קודקוד השורש שלו הופך לבן הזקונים של קודקוד היעד. כשהוא מוחזר- הוא הופך לבן הזקונים של קודקוד המקור. אם הוא לא היה מלכתחילה בן זקונים- הוא לא יחזור בדיוק לאותו מקום.. יש עוד מקום לשפר מעט את הפרוצדורה כך שתעביר לא לסוף אלא לראשוני הפנוי הראשון.
בדוגמה הנ"ל אין בעייה כי מלכתחילה בחרתי בבן זקונים.
סיכום: אם אצטרך לממש מודל היררכי- לא אמציא את הגלגל מחדש ולא אשתמש בשיטה הזו.. מדובר בתרגיל, מעניין מדי פעם לבדוק רעיונות מקוריים, ומי יודע? לעיתים נמצא לרעיונות אלו שימוש לא צפוי.
