矩陣乘法的并行化 實(shí)驗(yàn)報(bào)告.doc

北京科技大學(xué) 計(jì)算機(jī)與通信工程學(xué)院實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)名稱： 學(xué)生姓名： 專 業(yè)： 班 級(jí)： 學(xué) 號(hào)： 指導(dǎo)教師： 實(shí)驗(yàn)成績：_實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)時(shí)間：2015年05月一、實(shí)驗(yàn)?zāi)康呐c實(shí)驗(yàn)要求1、實(shí)驗(yàn)?zāi)康?對比矩陣乘法的串行和并行算法，查看運(yùn)行時(shí)間，得出相應(yīng)的結(jié)論；2觀察并行算法不同進(jìn)程數(shù)運(yùn)行結(jié)果，分析得出結(jié)論；2、實(shí)驗(yàn)要求1編寫矩陣乘法的串行程序，多次運(yùn)行得到結(jié)果匯總；2編寫基于MPI，分別實(shí)現(xiàn)矩陣乘法的并行化。對實(shí)現(xiàn)的并行程序進(jìn)行正確性測試和性能測試，并對測試結(jié)果進(jìn)行分析。二、實(shí)驗(yàn)設(shè)備（環(huán)境）及要求VS2013C+語言MPICH2三、實(shí)驗(yàn)內(nèi)容與步驟實(shí)驗(yàn)1，矩陣乘法的串行實(shí)驗(yàn)（1）實(shí)驗(yàn)內(nèi)容編寫串行程序，運(yùn)行匯總結(jié)果。（2）主要步驟按照正常的矩陣乘法計(jì)算方法，在VS2013上編寫矩陣乘法的串行程序，編譯后多次運(yùn)行，得到結(jié)果匯總。實(shí)驗(yàn)2矩陣乘法的并行化實(shí)驗(yàn)3個(gè)總進(jìn)程5個(gè)總進(jìn)程7個(gè)總進(jìn)程9個(gè)進(jìn)程16個(gè)進(jìn)程四：實(shí)驗(yàn)結(jié)果與分析（一）矩陣乘法并行化矩陣并行化算法分析：并行策略：1間隔行帶劃分法算法描述：將C=A*B中的A矩陣按行劃分，從進(jìn)程分得其中的幾行后同時(shí)進(jìn)行計(jì)算，最后通信將從進(jìn)程的結(jié)果合并的主進(jìn)程的C矩陣中對于矩陣A*B如圖：進(jìn)程1：矩陣A第一行 進(jìn)程2：矩陣A第二行 進(jìn)程3：矩陣A第三行 進(jìn)程1：矩陣A第四行時(shí)間復(fù)雜度分析：f(n) =6+2+8+k*n+k*n+k*n+3+10+n+k*n+k*n+n+2(k為從進(jìn)程分到的行數(shù))因此O(n)=(n)；空間復(fù)雜度分析：從進(jìn)程的存儲(chǔ)空間不共用，f(n)=n;因此O(n)=(n);2間隔行帶劃分法算法描述：將C=A*B中的A矩陣按行劃分，從進(jìn)程分得其中的幾行后同時(shí)進(jìn)行計(jì)算，最后通信將從進(jìn)程的結(jié)果合并的主進(jìn)程的C矩陣中對于矩陣A*B如圖：進(jìn)程1：矩陣A第一行 進(jìn)程2：矩陣A第二行 進(jìn)程3：矩陣A第三行 進(jìn)程3：矩陣A第四行時(shí)間復(fù)雜度分析：f(n) =6+2+8+k*n+k*n+k*n+3+10+n+k*n+k*n+n+2(k為從進(jìn)程分到的行數(shù))因此O(n)=(n)；空間復(fù)雜度分析：從進(jìn)程的存儲(chǔ)空間不共用，f(n)=n;因此T(n)=O(n);測試環(huán)境簡介：VS2013Win7旗艦版正確性測試結(jié)果：并行結(jié)果：串行結(jié)果：通過比較發(fā)現(xiàn)兩者相同，因此可以確定運(yùn)算結(jié)果正確。性能測試結(jié)果：串行125ms107ms108ms98ms109ms110ms3進(jìn)程0.009647ms0.009936ms0.010825ms0.009207ms0.008811ms0.009831ms5進(jìn)程0.007795ms0.007648ms0.008588ms0.008334ms0.007686ms0.007731ms7進(jìn)程0.010729ms0.011336ms0.011606ms0.011403ms0.011621ms0.014563ms9進(jìn)程0.016547ms0.014439ms0.016300ms0.015455ms0.015187ms0.011240ms16進(jìn)程0.024964ms0.027917ms0.024721ms0.028152ms0.022296ms0.021321ms通過對比分析得出，并行算法能夠有效提高矩陣乘法的運(yùn)算效率；（二）串行算法分析時(shí)間復(fù)雜度：f(n)=2+n2+2*n+3*n+7+n+n+7;因此T(n)=O(n2)空間復(fù)雜度：T（n）=O(1)五：結(jié)論（討論）1、 實(shí)驗(yàn)結(jié)論(1) 根據(jù)前面實(shí)驗(yàn)結(jié)果，可以證明并行算法比串行算法更能有效地運(yùn)算矩陣乘法，可以提高效率數(shù)十倍(2) 如下圖，根據(jù)結(jié)果可以得出并行程序并不是進(jìn)程數(shù)越多，程序運(yùn)行時(shí)間越短，程序運(yùn)行還受計(jì)算機(jī)運(yùn)算器數(shù)的限制2、討論1由于矩陣乘法的運(yùn)算并不是很復(fù)雜，因此運(yùn)算時(shí)間很短，達(dá)到了毫秒級(jí)，因此準(zhǔn)確度有一定的影響；2因?yàn)闀r(shí)間緊迫，未能進(jìn)一步分析代碼，同時(shí)只用了一種并行算法。六：代碼附錄串行算法：#include #include #include #include #define N 30#define M 30void juzhen_mul(int m, int n, int *p1M, int m1, int n1, int *p2M)int i, j, x = 0;int cNM = 0 ; 2for (i = 0; im;)for (j = 0; jm1; j+) cix += *(p1i + j)*(p2j + x); 30*30 m1*mprintf(%d, cix);printf( ); 2*30 2*mx+;if (x = n1)x = 0;i+;printf(n); 2*30 3*mvoid main()double start, finish;start = (double)clock();char H;int i, j;int *paM, *pbM;int m = 30, n = 30;int aMN = 90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12; 7for (i = 0; im; i+)pai = ai; mint bMN = 90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12;for (i = 0; im; i+)pbi = bi; mint m1 = 30, n1 = 30;printf(矩陣A*B= n);if (n = m1)juzhen_mul(m, n, pa, m1, n1, pb);elseprintf(輸入的行數(shù)和列數(shù)有誤，請重新輸入!n);finish = (double)clock();printf(程序運(yùn)行時(shí)間為：%lfmsn, double(finish - start) / CLOCKS_PER_SEC*1000);getchar(); 7并行#undef SEEK_SET#undef SEEK_END#undef SEEK_CUR#define MPICH_SKIP_MPICXX#include #include #include #include #include #include using namespace std;int master();int slave();int main(void) int myid; /int numprocs; /MPI_Status status;/MPI程序的初始化MPI_Init(NULL, NULL);/獲取當(dāng)前進(jìn)程的進(jìn)程編號(hào)，保存在myid中MPI_Comm_rank(MPI_COMM_WORLD, &myid);/獲取當(dāng)前進(jìn)程的進(jìn)程總數(shù)，保存在numprocs中MPI_Comm_size(MPI_COMM_WORLD, &numprocs); 6/如果進(jìn)程數(shù)小于2個(gè)，則退出程序if (numprocs2)cout Too Few Processes! endl;MPI_Abort(MPI_COMM_WORLD, 99); 2if (myid = 0)/id是0的進(jìn)程作為主進(jìn)程double start = MPI_Wtime();int myid; /int numprocs; /MPI_Status status;/獲取當(dāng)前進(jìn)程的進(jìn)程編號(hào)，保存在myid中MPI_Comm_rank(MPI_COMM_WORLD, &myid);/獲取當(dāng)前進(jìn)程的進(jìn)程總數(shù)，保存在numprocs中MPI_Comm_size(MPI_COMM_WORLD, &numprocs);int const M(30), K(30), N(30);/結(jié)果矩陣Cint CM*N;int VM; 8/將結(jié)果矩陣各元素初始化為0for (int i = 0; iM*N; i+)Ci = 0; M*N/C矩陣共N列數(shù)據(jù)for (int i = 0; iN; i+)/從各從進(jìn)程接受數(shù)據(jù)for (int j = 1; jnumprocs; j+)MPI_Recv(V, M, MPI_INT, j, i, MPI_COMM_WORLD, &status); n*num/將各從進(jìn)程的部分?jǐn)?shù)據(jù)整合成完整的一個(gè)向量for (int ij = 0; ijM; ij+)Cij*N + i = Cij*N + i + Vij; ij/打印結(jié)果for (int i = 0; iM; i+)for (int j = 0; jN; j+)cout Ci*N + j t; M*Ncout endl;double finish = MPI_Wtime();printf(程序運(yùn)行時(shí)間為：%lfmsn, double(finish - start) / CLOCKS_PER_SEC*1000);return 0; 3else/id是非0的進(jìn)程作為從進(jìn)程int myid; /int numprocs; /MPI_Status status;/獲取當(dāng)前進(jìn)程的進(jìn)程編號(hào)，保存在myid中MPI_Comm_rank(MPI_COMM_WORLD, &myid);/獲取當(dāng)前進(jìn)程的進(jìn)程總數(shù)，保存在numprocs中MPI_Comm_size(MPI_COMM_WORLD, &numprocs);int const M(30), K(30), N(30);vector indexes;int VM;int AM*K = 90,6,55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53, 46, 35, 12, 64,97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99,53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55,7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43,19,12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12;int BK*N = 90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 63, 28, 89, 43, 19, 12,90, 6, 55, 1, 81, 18, 40, 57, 43, 23, 51, 73, 97, 3, 89, 57, 98, 58, 7, 12, 72, 2, 35, 74, 60, 59, 23, 30, 67, 53,46, 35, 12, 64, 97, 21, 69, 31, 21, 77, 14, 64, 71, 97, 5, 46, 100, 57, 64, 34, 20, 3, 4, 5, 67, 20, 5, 41, 99, 53,63, 90, 70, 73, 34, 55, 42, 27, 1, 85, 32, 85, 26, 69, 91, 43, 31, 73, 32, 49, 15, 74, 79, 8, 90, 75, 8, 85, 49, 68,15, 38, 50, 39, 91, 22, 47, 97, 45, 82, 96, 66, 81, 40, 58, 75, 75, 26, 61, 59, 51, 17, 66, 56, 20, 39, 62, 29, 57, 94,81, 34, 9, 54, 58, 33, 96, 2, 55, 7, 38, 43, 87, 19, 72, 91, 16, 28, 53, 12, 76, 39, 50, 99, 6