#include <iostream>
#include <stdint.h>
#include <stdio.h>
 
using namespace std;
 
// класс, реализующий матрицу
class Matrix
{
   public:
 
      // конструктор по умолчанию
      Matrix()
      : mNumRows(0)
      , mNumCols(0)
      , mArr(0)
      {
      }
 
      // конструктор, создающий реальную матрицу ненулевой размерности и заполняет начальным значением
      Matrix( int numRows, int numCols, double initValue )
      : mNumRows( 0 )
      , mNumCols( 0 )
      , mArr( 0 )
      {
         initArr( numRows, numCols, initValue );
      }
 
      // конструктор копии - создающий матрицу как копию матрици-источника
      Matrix( Matrix& source )
      : mNumRows( source.mNumRows )
      , mNumCols( source.mNumCols )
      , mArr( 0 )
      {
         swap( source );
      }
 
      // деструктор, необходим для удаления выделенного на куче двумерного массива
      ~Matrix()
      {
         resetArr();
      }
 
      // переопределённый оператор присваивания, необходим для корректного присваивания матриц
      Matrix& operator=( Matrix& rhs )
      {
         swap( rhs );
      }
 
      // возвращает число строк в матрице
      int getNumRows() { return mNumRows; };
 
      // возвращает число колонок в матрице
      int getNumCols() { return mNumCols; };
 
      // возвращает указатель на двумерный массив на куче, содержащий саму матрицу
      double** getArr() { return mArr; };
 
      // копирует матрицу-источник в себя
      void swap( Matrix& another );
 
      // создает левую диагональ, заполненную заданным значением
      void setLeftDiag( double value );
 
      // суммирует другую матрицу с собой
      void sum( Matrix& another );
 
      // возводит себя в n-ю степень
      void power( int n );
 
      //выполняет произведение себя и другой матрицы, метод используется в методе power
      void product( Matrix& another );
 
      // умножает себя на заданное значение
      void multiply( double& value );
 
      // выводит на консоль содержимое себя, придворенное заголовком
      void show( const char* title );
 
      // создает заново свой двумерный массив и заполняет заданным значеним, исп. в конструкторе
      void initArr( int numRows, int numCols, double initValue );
 
      // удаляет двумерный массив из кучи и обнуляет указатель, исп. в деструкторе а также в initArr
      void resetArr();
 
   private:
 
      int mNumRows;
      int mNumCols;
      double** mArr;
};
 
void Matrix::swap( Matrix& another )
{
   initArr( another.mNumRows, another.mNumCols, 0 );
   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         mArr[ row ][ col ] = another.mArr[ row ][ col ];
      }
   }
}
 
void Matrix::setLeftDiag( double value )
{
   int n = min( mNumRows, mNumCols );
   for( int i = 0; i < n; i++ )
   {
      mArr[ i ][ i ] = value;
   }
}
 
void Matrix::sum( Matrix& another )
{
   int numRows = min( mNumRows, another.getNumRows() );
   int numCols = min( mNumCols, another.getNumCols() );
 
   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         mArr[ row ][ col ] += another.mArr[ row ][ col ];
      }
   }
}
 
void Matrix::power( int n )
{
   for( int i = 1; i < n; i++ )
   {
      product( *this );
   }
}
 
void Matrix::product( Matrix& another )
{
 
   if ( mNumCols != another.mNumRows )
   {
      printf( "*** Matrix::product: argument matrix is not complementary, production is impossible ***\n" );
      return;
   }
 
   Matrix result( mNumRows, another.mNumCols, 0 ); 
 
   for( int rowResult = 0; rowResult < result.mNumRows; rowResult++ )
   {
      for( int colResult = 0; colResult < result.mNumCols; colResult++ )
      {
         result.mArr[ rowResult ][ colResult ] = 0;
         for( int col = 0; col < mNumCols; col++ )
         {
 
            result.mArr[ rowResult ][ colResult ] +=
               ( mArr[ rowResult ][ col ] * another.mArr[ col ][ colResult ] );
         }
      }
   }
 
   swap( result );
} 
 
void Matrix::multiply( double& value )
{
   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         mArr[ row ][ col ] *= value;
      }
   }
}
 
void Matrix::show( const char* title )
{
   printf("%s:\n", title);
 
   for( int row = 0; row < mNumRows; row++ )
   {
      for( int col = 0; col < mNumCols; col++ )
      {
         printf("%10.04lf ", mArr[ row ][ col ] );
      }
      printf("\n");
   }
}
 
void Matrix::initArr( int numRows, int numCols, double initValue )
{
   resetArr();
   mNumRows = numRows;
   mNumCols = numCols;
   mArr = new double*[ mNumRows ]; // создает массив указателей на подмассивы колонок
   for( int row = 0; row < mNumRows; row++ )
   {
      mArr[ row ] = new double[ mNumCols ]; // создает подмассив колонок для данной строки
      for( int col = 0; col < mNumCols; col++ ) // заполняет подмассив колонок заданным значениям
      {
         mArr[ row ][ col ] = initValue;
      }
   }
}
 
void Matrix::resetArr()
{
   if ( mArr!= 0 )
   {
      for( int row = 0; row < mNumRows; row++ )
      {
         delete[] mArr[ row ];
      }
      delete [] mArr;
      mArr = 0;
   }
}
 
//==============================================================================
 
// ввыд с консоли какого либо целого числа
static int inputNumber( const char *title )
{
   int n = 0;
 
   printf("input %s:\n", title);
 
   if ( scanf("%d", &n ) <= 0 )
   {
      printf("error input of %s\n",title);
   }
   else
   if ( n <= 0 )
   {
      printf("wrong %s value, must be positive\n", title);
   }
 
   return n;
}
 
// ввод с консоли содержимого какой либо матрицы
static bool inputMatrixData( const char *title, Matrix& x )
{
   printf("input %dx%d %s:\n", x.getNumRows(), x.getNumCols(), title );
 
   for( int row = 0; row < x.getNumRows(); row++ )
   {
      for( int col = 0; col < x.getNumCols(); col++ )
      {
         double val = 0;
         if ( scanf("%lf", &val ) <= 0 )
         {
            printf("error input of %s\n",title);
            return false;
         }
         x.getArr()[ row ][ col ] = val;
 
      }
   }
   return true;
}
 
//==============================================================================
 
int main()
{
   int numIter = inputNumber( "Number of iterations 'n'" );
   int sizeA   = inputNumber( "matrix size 'm'" );
 
   if ( numIter <= 0 || sizeA <= 0 )
   {
      return 0;
   }
 
   Matrix mxP( 1, numIter, 0 ); // для хранения p_0, P_1, ... P_n
   if ( ! inputMatrixData( "P matrix values", mxP ) )
   {
      return 0;
   }
 
   Matrix mxA( sizeA, sizeA, 0 );
   if ( ! inputMatrixData( "A matrix values", mxA ) )
   {
      return 0;
   }
 
   Matrix mxE( sizeA, sizeA, 0 );
   mxE.setLeftDiag( 1 );
 
   // печатаем исходные данные перед вычислением
   mxE.show("============= matrix E ==============");
   mxP.show("============= matrix P ==============");
   mxA.show("============= matrix A ==============");
 
   Matrix s; // это будет общая сумма полинома
 
   s.swap( mxE );
 
   s.multiply( mxP.getArr()[0][0] ); // создает P_0*E, как начальное значение суммирования
 
   // главный цикл суммирования полинома
   for( int i = 1; i < numIter; i++ )
   {
 
      Matrix x;  // это будет временная матрица для вычисления одного слагаемого полинома (pow(A,i)*P_i*E)
      x.swap( mxA ); // копируем содержимое матрицы A
 
      x.power( i );  // возводим x в степень i, т.е. pow(A,i)
 
      x.multiply( mxP.getArr()[0][i] ); // умножаем x на коэфф. p_i , т.е. полуйчаем результат одного слогаемого (pow(A,i)*P_i)
 
      s.sum( x ); // накапливаем сумму полинома
 
   }
 
   s.show("============= result: ==============");// печатаем результат вычисления полинома
 
   return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RkaW50Lmg+CiNpbmNsdWRlIDxzdGRpby5oPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vINC60LvQsNGB0YEsINGA0LXQsNC70LjQt9GD0Y7RidC40Lkg0LzQsNGC0YDQuNGG0YMKY2xhc3MgTWF0cml4CnsKICAgcHVibGljOgoKICAgICAgLy8g0LrQvtC90YHRgtGA0YPQutGC0L7RgCDQv9C+INGD0LzQvtC70YfQsNC90LjRjgogICAgICBNYXRyaXgoKQogICAgICA6IG1OdW1Sb3dzKDApCiAgICAgICwgbU51bUNvbHMoMCkKICAgICAgLCBtQXJyKDApCiAgICAgIHsKICAgICAgfQoKICAgICAgLy8g0LrQvtC90YHRgtGA0YPQutGC0L7RgCwg0YHQvtC30LTQsNGO0YnQuNC5INGA0LXQsNC70YzQvdGD0Y4g0LzQsNGC0YDQuNGG0YMg0L3QtdC90YPQu9C10LLQvtC5INGA0LDQt9C80LXRgNC90L7RgdGC0Lgg0Lgg0LfQsNC/0L7Qu9C90Y/QtdGCINC90LDRh9Cw0LvRjNC90YvQvCDQt9C90LDRh9C10L3QuNC10LwKICAgICAgTWF0cml4KCBpbnQgbnVtUm93cywgaW50IG51bUNvbHMsIGRvdWJsZSBpbml0VmFsdWUgKQogICAgICA6IG1OdW1Sb3dzKCAwICkKICAgICAgLCBtTnVtQ29scyggMCApCiAgICAgICwgbUFyciggMCApCiAgICAgIHsKICAgICAgICAgaW5pdEFyciggbnVtUm93cywgbnVtQ29scywgaW5pdFZhbHVlICk7CiAgICAgIH0KICAgICAgCiAgICAgIC8vINC60L7QvdGB0YLRgNGD0LrRgtC+0YAg0LrQvtC/0LjQuCAtINGB0L7Qt9C00LDRjtGJ0LjQuSDQvNCw0YLRgNC40YbRgyDQutCw0Log0LrQvtC/0LjRjiDQvNCw0YLRgNC40YbQuC3QuNGB0YLQvtGH0L3QuNC60LAKICAgICAgTWF0cml4KCBNYXRyaXgmIHNvdXJjZSApCiAgICAgIDogbU51bVJvd3MoIHNvdXJjZS5tTnVtUm93cyApCiAgICAgICwgbU51bUNvbHMoIHNvdXJjZS5tTnVtQ29scyApCiAgICAgICwgbUFyciggMCApCiAgICAgIHsKICAgICAgICAgc3dhcCggc291cmNlICk7CiAgICAgIH0KCiAgICAgIC8vINC00LXRgdGC0YDRg9C60YLQvtGALCDQvdC10L7QsdGF0L7QtNC40Lwg0LTQu9GPINGD0LTQsNC70LXQvdC40Y8g0LLRi9C00LXQu9C10L3QvdC+0LPQviDQvdCwINC60YPRh9C1INC00LLRg9C80LXRgNC90L7Qs9C+INC80LDRgdGB0LjQstCwCiAgICAgIH5NYXRyaXgoKQogICAgICB7CiAgICAgICAgIHJlc2V0QXJyKCk7CiAgICAgIH0KCiAgICAgIC8vINC/0LXRgNC10L7Qv9GA0LXQtNC10LvRkdC90L3Ri9C5INC+0L/QtdGA0LDRgtC+0YAg0L/RgNC40YHQstCw0LjQstCw0L3QuNGPLCDQvdC10L7QsdGF0L7QtNC40Lwg0LTQu9GPINC60L7RgNGA0LXQutGC0L3QvtCz0L4g0L/RgNC40YHQstCw0LjQstCw0L3QuNGPINC80LDRgtGA0LjRhgogICAgICBNYXRyaXgmIG9wZXJhdG9yPSggTWF0cml4JiByaHMgKQogICAgICB7CiAgICAgICAgIHN3YXAoIHJocyApOwogICAgICB9CgogICAgICAvLyDQstC+0LfQstGA0LDRidCw0LXRgiDRh9C40YHQu9C+INGB0YLRgNC+0Log0LIg0LzQsNGC0YDQuNGG0LUKICAgICAgaW50IGdldE51bVJvd3MoKSB7IHJldHVybiBtTnVtUm93czsgfTsKCiAgICAgIC8vINCy0L7Qt9Cy0YDQsNGJ0LDQtdGCINGH0LjRgdC70L4g0LrQvtC70L7QvdC+0Log0LIg0LzQsNGC0YDQuNGG0LUKICAgICAgaW50IGdldE51bUNvbHMoKSB7IHJldHVybiBtTnVtQ29sczsgfTsKCiAgICAgIC8vINCy0L7Qt9Cy0YDQsNGJ0LDQtdGCINGD0LrQsNC30LDRgtC10LvRjCDQvdCwINC00LLRg9C80LXRgNC90YvQuSDQvNCw0YHRgdC40LIg0L3QsCDQutGD0YfQtSwg0YHQvtC00LXRgNC20LDRidC40Lkg0YHQsNC80YMg0LzQsNGC0YDQuNGG0YMKICAgICAgZG91YmxlKiogZ2V0QXJyKCkgeyByZXR1cm4gbUFycjsgfTsKCiAgICAgIC8vINC60L7Qv9C40YDRg9C10YIg0LzQsNGC0YDQuNGG0YMt0LjRgdGC0L7Rh9C90LjQuiDQsiDRgdC10LHRjwogICAgICB2b2lkIHN3YXAoIE1hdHJpeCYgYW5vdGhlciApOwoKICAgICAgLy8g0YHQvtC30LTQsNC10YIg0LvQtdCy0YPRjiDQtNC40LDQs9C+0L3QsNC70YwsINC30LDQv9C+0LvQvdC10L3QvdGD0Y4g0LfQsNC00LDQvdC90YvQvCDQt9C90LDRh9C10L3QuNC10LwKICAgICAgdm9pZCBzZXRMZWZ0RGlhZyggZG91YmxlIHZhbHVlICk7CgogICAgICAvLyDRgdGD0LzQvNC40YDRg9C10YIg0LTRgNGD0LPRg9GOINC80LDRgtGA0LjRhtGDINGBINGB0L7QsdC+0LkKICAgICAgdm9pZCBzdW0oIE1hdHJpeCYgYW5vdGhlciApOwoKICAgICAgLy8g0LLQvtC30LLQvtC00LjRgiDRgdC10LHRjyDQsiBuLdGOINGB0YLQtdC/0LXQvdGMCiAgICAgIHZvaWQgcG93ZXIoIGludCBuICk7CgogICAgICAvL9Cy0YvQv9C+0LvQvdGP0LXRgiDQv9GA0L7QuNC30LLQtdC00LXQvdC40LUg0YHQtdCx0Y8g0Lgg0LTRgNGD0LPQvtC5INC80LDRgtGA0LjRhtGLLCDQvNC10YLQvtC0INC40YHQv9C+0LvRjNC30YPQtdGC0YHRjyDQsiDQvNC10YLQvtC00LUgcG93ZXIKICAgICAgdm9pZCBwcm9kdWN0KCBNYXRyaXgmIGFub3RoZXIgKTsKCiAgICAgIC8vINGD0LzQvdC+0LbQsNC10YIg0YHQtdCx0Y8g0L3QsCDQt9Cw0LTQsNC90L3QvtC1INC30L3QsNGH0LXQvdC40LUKICAgICAgdm9pZCBtdWx0aXBseSggZG91YmxlJiB2YWx1ZSApOwoKICAgICAgLy8g0LLRi9Cy0L7QtNC40YIg0L3QsCDQutC+0L3RgdC+0LvRjCDRgdC+0LTQtdGA0LbQuNC80L7QtSDRgdC10LHRjywg0L/RgNC40LTQstC+0YDQtdC90L3QvtC1INC30LDQs9C+0LvQvtCy0LrQvtC8CiAgICAgIHZvaWQgc2hvdyggY29uc3QgY2hhciogdGl0bGUgKTsKCiAgICAgIC8vINGB0L7Qt9C00LDQtdGCINC30LDQvdC+0LLQviDRgdCy0L7QuSDQtNCy0YPQvNC10YDQvdGL0Lkg0LzQsNGB0YHQuNCyINC4INC30LDQv9C+0LvQvdGP0LXRgiDQt9Cw0LTQsNC90L3Ri9C8INC30L3QsNGH0LXQvdC40LwsINC40YHQvy4g0LIg0LrQvtC90YHRgtGA0YPQutGC0L7RgNC1CiAgICAgIHZvaWQgaW5pdEFyciggaW50IG51bVJvd3MsIGludCBudW1Db2xzLCBkb3VibGUgaW5pdFZhbHVlICk7CgogICAgICAvLyDRg9C00LDQu9GP0LXRgiDQtNCy0YPQvNC10YDQvdGL0Lkg0LzQsNGB0YHQuNCyINC40Lcg0LrRg9GH0Lgg0Lgg0L7QsdC90YPQu9GP0LXRgiDRg9C60LDQt9Cw0YLQtdC70YwsINC40YHQvy4g0LIg0LTQtdGB0YLRgNGD0LrRgtC+0YDQtSDQsCDRgtCw0LrQttC1INCyIGluaXRBcnIKICAgICAgdm9pZCByZXNldEFycigpOwoKICAgcHJpdmF0ZToKCiAgICAgIGludCBtTnVtUm93czsKICAgICAgaW50IG1OdW1Db2xzOwogICAgICBkb3VibGUqKiBtQXJyOwp9OwoKdm9pZCBNYXRyaXg6OnN3YXAoIE1hdHJpeCYgYW5vdGhlciApCnsKICAgaW5pdEFyciggYW5vdGhlci5tTnVtUm93cywgYW5vdGhlci5tTnVtQ29scywgMCApOwogICBmb3IoIGludCByb3cgPSAwOyByb3cgPCBtTnVtUm93czsgcm93KysgKQogICB7CiAgICAgIGZvciggaW50IGNvbCA9IDA7IGNvbCA8IG1OdW1Db2xzOyBjb2wrKyApCiAgICAgIHsKICAgICAgICAgbUFyclsgcm93IF1bIGNvbCBdID0gYW5vdGhlci5tQXJyWyByb3cgXVsgY29sIF07CiAgICAgIH0KICAgfQp9Cgp2b2lkIE1hdHJpeDo6c2V0TGVmdERpYWcoIGRvdWJsZSB2YWx1ZSApCnsKICAgaW50IG4gPSBtaW4oIG1OdW1Sb3dzLCBtTnVtQ29scyApOwogICBmb3IoIGludCBpID0gMDsgaSA8IG47IGkrKyApCiAgIHsKICAgICAgbUFyclsgaSBdWyBpIF0gPSB2YWx1ZTsKICAgfQp9Cgp2b2lkIE1hdHJpeDo6c3VtKCBNYXRyaXgmIGFub3RoZXIgKQp7CiAgIGludCBudW1Sb3dzID0gbWluKCBtTnVtUm93cywgYW5vdGhlci5nZXROdW1Sb3dzKCkgKTsKICAgaW50IG51bUNvbHMgPSBtaW4oIG1OdW1Db2xzLCBhbm90aGVyLmdldE51bUNvbHMoKSApOwoKICAgZm9yKCBpbnQgcm93ID0gMDsgcm93IDwgbU51bVJvd3M7IHJvdysrICkKICAgewogICAgICBmb3IoIGludCBjb2wgPSAwOyBjb2wgPCBtTnVtQ29sczsgY29sKysgKQogICAgICB7CiAgICAgICAgIG1BcnJbIHJvdyBdWyBjb2wgXSArPSBhbm90aGVyLm1BcnJbIHJvdyBdWyBjb2wgXTsKICAgICAgfQogICB9Cn0KCnZvaWQgTWF0cml4Ojpwb3dlciggaW50IG4gKQp7CiAgIGZvciggaW50IGkgPSAxOyBpIDwgbjsgaSsrICkKICAgewogICAgICBwcm9kdWN0KCAqdGhpcyApOwogICB9Cn0KCnZvaWQgTWF0cml4Ojpwcm9kdWN0KCBNYXRyaXgmIGFub3RoZXIgKQp7CgogICBpZiAoIG1OdW1Db2xzICE9IGFub3RoZXIubU51bVJvd3MgKQogICB7CiAgICAgIHByaW50ZiggIioqKiBNYXRyaXg6OnByb2R1Y3Q6IGFyZ3VtZW50IG1hdHJpeCBpcyBub3QgY29tcGxlbWVudGFyeSwgcHJvZHVjdGlvbiBpcyBpbXBvc3NpYmxlICoqKlxuIiApOwogICAgICByZXR1cm47CiAgIH0KCiAgIE1hdHJpeCByZXN1bHQoIG1OdW1Sb3dzLCBhbm90aGVyLm1OdW1Db2xzLCAwICk7IAoKICAgZm9yKCBpbnQgcm93UmVzdWx0ID0gMDsgcm93UmVzdWx0IDwgcmVzdWx0Lm1OdW1Sb3dzOyByb3dSZXN1bHQrKyApCiAgIHsKICAgICAgZm9yKCBpbnQgY29sUmVzdWx0ID0gMDsgY29sUmVzdWx0IDwgcmVzdWx0Lm1OdW1Db2xzOyBjb2xSZXN1bHQrKyApCiAgICAgIHsKICAgICAgICAgcmVzdWx0Lm1BcnJbIHJvd1Jlc3VsdCBdWyBjb2xSZXN1bHQgXSA9IDA7CiAgICAgICAgIGZvciggaW50IGNvbCA9IDA7IGNvbCA8IG1OdW1Db2xzOyBjb2wrKyApCiAgICAgICAgIHsKCiAgICAgICAgICAgIHJlc3VsdC5tQXJyWyByb3dSZXN1bHQgXVsgY29sUmVzdWx0IF0gKz0KICAgICAgICAgICAgICAgKCBtQXJyWyByb3dSZXN1bHQgXVsgY29sIF0gKiBhbm90aGVyLm1BcnJbIGNvbCBdWyBjb2xSZXN1bHQgXSApOwogICAgICAgICB9CiAgICAgIH0KICAgfQoKICAgc3dhcCggcmVzdWx0ICk7Cn0gCgp2b2lkIE1hdHJpeDo6bXVsdGlwbHkoIGRvdWJsZSYgdmFsdWUgKQp7CiAgIGZvciggaW50IHJvdyA9IDA7IHJvdyA8IG1OdW1Sb3dzOyByb3crKyApCiAgIHsKICAgICAgZm9yKCBpbnQgY29sID0gMDsgY29sIDwgbU51bUNvbHM7IGNvbCsrICkKICAgICAgewogICAgICAgICBtQXJyWyByb3cgXVsgY29sIF0gKj0gdmFsdWU7CiAgICAgIH0KICAgfQp9Cgp2b2lkIE1hdHJpeDo6c2hvdyggY29uc3QgY2hhciogdGl0bGUgKQp7CiAgIHByaW50ZigiJXM6XG4iLCB0aXRsZSk7CgogICBmb3IoIGludCByb3cgPSAwOyByb3cgPCBtTnVtUm93czsgcm93KysgKQogICB7CiAgICAgIGZvciggaW50IGNvbCA9IDA7IGNvbCA8IG1OdW1Db2xzOyBjb2wrKyApCiAgICAgIHsKICAgICAgICAgcHJpbnRmKCIlMTAuMDRsZiAiLCBtQXJyWyByb3cgXVsgY29sIF0gKTsKICAgICAgfQogICAgICBwcmludGYoIlxuIik7CiAgIH0KfQoKdm9pZCBNYXRyaXg6OmluaXRBcnIoIGludCBudW1Sb3dzLCBpbnQgbnVtQ29scywgZG91YmxlIGluaXRWYWx1ZSApCnsKICAgcmVzZXRBcnIoKTsKICAgbU51bVJvd3MgPSBudW1Sb3dzOwogICBtTnVtQ29scyA9IG51bUNvbHM7CiAgIG1BcnIgPSBuZXcgZG91YmxlKlsgbU51bVJvd3MgXTsgLy8g0YHQvtC30LTQsNC10YIg0LzQsNGB0YHQuNCyINGD0LrQsNC30LDRgtC10LvQtdC5INC90LAg0L/QvtC00LzQsNGB0YHQuNCy0Ysg0LrQvtC70L7QvdC+0LoKICAgZm9yKCBpbnQgcm93ID0gMDsgcm93IDwgbU51bVJvd3M7IHJvdysrICkKICAgewogICAgICBtQXJyWyByb3cgXSA9IG5ldyBkb3VibGVbIG1OdW1Db2xzIF07IC8vINGB0L7Qt9C00LDQtdGCINC/0L7QtNC80LDRgdGB0LjQsiDQutC+0LvQvtC90L7QuiDQtNC70Y8g0LTQsNC90L3QvtC5INGB0YLRgNC+0LrQuAogICAgICBmb3IoIGludCBjb2wgPSAwOyBjb2wgPCBtTnVtQ29sczsgY29sKysgKSAvLyDQt9Cw0L/QvtC70L3Rj9C10YIg0L/QvtC00LzQsNGB0YHQuNCyINC60L7Qu9C+0L3QvtC6INC30LDQtNCw0L3QvdGL0Lwg0LfQvdCw0YfQtdC90LjRj9C8CiAgICAgIHsKICAgICAgICAgbUFyclsgcm93IF1bIGNvbCBdID0gaW5pdFZhbHVlOwogICAgICB9CiAgIH0KfQoKdm9pZCBNYXRyaXg6OnJlc2V0QXJyKCkKewogICBpZiAoIG1BcnIhPSAwICkKICAgewogICAgICBmb3IoIGludCByb3cgPSAwOyByb3cgPCBtTnVtUm93czsgcm93KysgKQogICAgICB7CiAgICAgICAgIGRlbGV0ZVtdIG1BcnJbIHJvdyBdOwogICAgICB9CiAgICAgIGRlbGV0ZSBbXSBtQXJyOwogICAgICBtQXJyID0gMDsKICAgfQp9CgovLz09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQoKLy8g0LLQstGL0LQg0YEg0LrQvtC90YHQvtC70Lgg0LrQsNC60L7Qs9C+INC70LjQsdC+INGG0LXQu9C+0LPQviDRh9C40YHQu9CwCnN0YXRpYyBpbnQgaW5wdXROdW1iZXIoIGNvbnN0IGNoYXIgKnRpdGxlICkKewogICBpbnQgbiA9IDA7CgogICBwcmludGYoImlucHV0ICVzOlxuIiwgdGl0bGUpOwoKICAgaWYgKCBzY2FuZigiJWQiLCAmbiApIDw9IDAgKQogICB7CiAgICAgIHByaW50ZigiZXJyb3IgaW5wdXQgb2YgJXNcbiIsdGl0bGUpOwogICB9CiAgIGVsc2UKICAgaWYgKCBuIDw9IDAgKQogICB7CiAgICAgIHByaW50Zigid3JvbmcgJXMgdmFsdWUsIG11c3QgYmUgcG9zaXRpdmVcbiIsIHRpdGxlKTsKICAgfQoKICAgcmV0dXJuIG47Cn0KCi8vINCy0LLQvtC0INGBINC60L7QvdGB0L7Qu9C4INGB0L7QtNC10YDQttC40LzQvtCz0L4g0LrQsNC60L7QuSDQu9C40LHQviDQvNCw0YLRgNC40YbRiwpzdGF0aWMgYm9vbCBpbnB1dE1hdHJpeERhdGEoIGNvbnN0IGNoYXIgKnRpdGxlLCBNYXRyaXgmIHggKQp7CiAgIHByaW50ZigiaW5wdXQgJWR4JWQgJXM6XG4iLCB4LmdldE51bVJvd3MoKSwgeC5nZXROdW1Db2xzKCksIHRpdGxlICk7CgogICBmb3IoIGludCByb3cgPSAwOyByb3cgPCB4LmdldE51bVJvd3MoKTsgcm93KysgKQogICB7CiAgICAgIGZvciggaW50IGNvbCA9IDA7IGNvbCA8IHguZ2V0TnVtQ29scygpOyBjb2wrKyApCiAgICAgIHsKICAgICAgICAgZG91YmxlIHZhbCA9IDA7CiAgICAgICAgIGlmICggc2NhbmYoIiVsZiIsICZ2YWwgKSA8PSAwICkKICAgICAgICAgewogICAgICAgICAgICBwcmludGYoImVycm9yIGlucHV0IG9mICVzXG4iLHRpdGxlKTsKICAgICAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgICAgICB9CiAgICAgICAgIHguZ2V0QXJyKClbIHJvdyBdWyBjb2wgXSA9IHZhbDsKCiAgICAgIH0KICAgfQogICByZXR1cm4gdHJ1ZTsKfQoKLy89PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KCmludCBtYWluKCkKewogICBpbnQgbnVtSXRlciA9IGlucHV0TnVtYmVyKCAiTnVtYmVyIG9mIGl0ZXJhdGlvbnMgJ24nIiApOwogICBpbnQgc2l6ZUEgICA9IGlucHV0TnVtYmVyKCAibWF0cml4IHNpemUgJ20nIiApOwoKICAgaWYgKCBudW1JdGVyIDw9IDAgfHwgc2l6ZUEgPD0gMCApCiAgIHsKICAgICAgcmV0dXJuIDA7CiAgIH0KCiAgIE1hdHJpeCBteFAoIDEsIG51bUl0ZXIsIDAgKTsgLy8g0LTQu9GPINGF0YDQsNC90LXQvdC40Y8gcF8wLCBQXzEsIC4uLiBQX24KICAgaWYgKCAhIGlucHV0TWF0cml4RGF0YSggIlAgbWF0cml4IHZhbHVlcyIsIG14UCApICkKICAgewogICAgICByZXR1cm4gMDsKICAgfQoKICAgTWF0cml4IG14QSggc2l6ZUEsIHNpemVBLCAwICk7CiAgIGlmICggISBpbnB1dE1hdHJpeERhdGEoICJBIG1hdHJpeCB2YWx1ZXMiLCBteEEgKSApCiAgIHsKICAgICAgcmV0dXJuIDA7CiAgIH0KCiAgIE1hdHJpeCBteEUoIHNpemVBLCBzaXplQSwgMCApOwogICBteEUuc2V0TGVmdERpYWcoIDEgKTsKCiAgIC8vINC/0LXRh9Cw0YLQsNC10Lwg0LjRgdGF0L7QtNC90YvQtSDQtNCw0L3QvdGL0LUg0L/QtdGA0LXQtCDQstGL0YfQuNGB0LvQtdC90LjQtdC8CiAgIG14RS5zaG93KCI9PT09PT09PT09PT09IG1hdHJpeCBFID09PT09PT09PT09PT09Iik7CiAgIG14UC5zaG93KCI9PT09PT09PT09PT09IG1hdHJpeCBQID09PT09PT09PT09PT09Iik7CiAgIG14QS5zaG93KCI9PT09PT09PT09PT09IG1hdHJpeCBBID09PT09PT09PT09PT09Iik7CgogICBNYXRyaXggczsgLy8g0Y3RgtC+INCx0YPQtNC10YIg0L7QsdGJ0LDRjyDRgdGD0LzQvNCwINC/0L7Qu9C40L3QvtC80LAKCiAgIHMuc3dhcCggbXhFICk7CgogICBzLm11bHRpcGx5KCBteFAuZ2V0QXJyKClbMF1bMF0gKTsgLy8g0YHQvtC30LTQsNC10YIgUF8wKkUsINC60LDQuiDQvdCw0YfQsNC70YzQvdC+0LUg0LfQvdCw0YfQtdC90LjQtSDRgdGD0LzQvNC40YDQvtCy0LDQvdC40Y8KCiAgIC8vINCz0LvQsNCy0L3Ri9C5INGG0LjQutC7INGB0YPQvNC80LjRgNC+0LLQsNC90LjRjyDQv9C+0LvQuNC90L7QvNCwCiAgIGZvciggaW50IGkgPSAxOyBpIDwgbnVtSXRlcjsgaSsrICkKICAgewogICAgCiAgICAgIE1hdHJpeCB4OyAgLy8g0Y3RgtC+INCx0YPQtNC10YIg0LLRgNC10LzQtdC90L3QsNGPINC80LDRgtGA0LjRhtCwINC00LvRjyDQstGL0YfQuNGB0LvQtdC90LjRjyDQvtC00L3QvtCz0L4g0YHQu9Cw0LPQsNC10LzQvtCz0L4g0L/QvtC70LjQvdC+0LzQsCAocG93KEEsaSkqUF9pKkUpCiAgICAgIHguc3dhcCggbXhBICk7IC8vINC60L7Qv9C40YDRg9C10Lwg0YHQvtC00LXRgNC20LjQvNC+0LUg0LzQsNGC0YDQuNGG0YsgQQoKICAgICAgeC5wb3dlciggaSApOyAgLy8g0LLQvtC30LLQvtC00LjQvCB4INCyINGB0YLQtdC/0LXQvdGMIGksINGCLtC1LiBwb3coQSxpKQoKICAgICAgeC5tdWx0aXBseSggbXhQLmdldEFycigpWzBdW2ldICk7IC8vINGD0LzQvdC+0LbQsNC10LwgeCDQvdCwINC60L7RjdGE0YQuIHBfaSAsINGCLtC1LiDQv9C+0LvRg9C50YfQsNC10Lwg0YDQtdC30YPQu9GM0YLQsNGCINC+0LTQvdC+0LPQviDRgdC70L7Qs9Cw0LXQvNC+0LPQviAocG93KEEsaSkqUF9pKQoKICAgICAgcy5zdW0oIHggKTsgLy8g0L3QsNC60LDQv9C70LjQstCw0LXQvCDRgdGD0LzQvNGDINC/0L7Qu9C40L3QvtC80LAKCiAgIH0KCiAgIHMuc2hvdygiPT09PT09PT09PT09PSByZXN1bHQ6ID09PT09PT09PT09PT09Iik7Ly8g0L/QtdGH0LDRgtCw0LXQvCDRgNC10LfRg9C70YzRgtCw0YIg0LLRi9GH0LjRgdC70LXQvdC40Y8g0L/QvtC70LjQvdC+0LzQsAogICAKICAgcmV0dXJuIDA7Cn0=