// 2^(2^34 - 1) = 2^17179869183 を計算する。
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <assert.h>
#include <stdarg.h>
#include <vector>
#include <utility>
#include <numeric>
 
#include <omp.h>
 
// [DBGSW] 中間結果表示
//#define SHOW_ITM
 
// [DBGSW] I表示
//#define SHOW_I
 
// [DBGSW] SIN_TABLE作成状況表示
//#define SHOW_SIN_TABLE
 
// [DBGSW] 消費時間表示
#define SHOW_CSM_TIME
 
// [DBGSW] 計算途中結果の保存
//#define SAVE_ITM_RESULT
 
typedef uint32_t I_TYPE;
 
// [CONF] 基本SINテーブルの最大要素数
#define BASIC_SINTBL_P_MAX		29
 
// [CONF] 多倍長バッファ1要素の10進数での桁数
const int FIG = 5;
 
// [CONF] 10^FIG
const I_TYPE RADIX = 100000;
 
// [CONF] 使用するCPUのL2キャッシュサイズ(2の冪 Byte/コア)の指数
#ifdef NDEBUG
#define EXPN_L2CHACHE_SZ			18			/* 256 KB */
#else
#define EXPN_L2CHACHE_SZ			8			/* 256 Byte (DEBUG) */
#endif
 
// [CONF] 同一L2キャッシュを共用するスレッドの数(2の冪)の指数
// Core i7 (HT有り)では1、Core i5 (HT無し)では0
#define EXPN_L2_SHARING_THREADS		1
 
// [CONF] sizeof(複素数) (2の冪)の指数(double 2個で16 Byte)
#define EXPN_SIZEOF_COMPLEX			4
 
static_assert((size_t)1 << EXPN_SIZEOF_COMPLEX == 2 * sizeof(double), "*** ERR ***");
 
// L2キャッシュにsrcとdstの両方が複素数が乗る最大要素数
#define EXPN_CAPACITY	(EXPN_L2CHACHE_SZ - EXPN_SIZEOF_COMPLEX - EXPN_L2_SHARING_THREADS - 1)
 
#ifdef _WIN32
int fopen_s_wrp(FILE** const p_fp, const char* const fpath, const char* const mode)
{
	return (int)fopen_s(p_fp, fpath, mode);
}
int sprintf_s_wrp(char buf[], const size_t bufsz, const char* const fmt, ...)
{
	va_list ap;
	int nRet;
 
	va_start(ap, fmt);
	nRet = vsprintf_s(buf, bufsz, fmt, ap);
	va_end(ap);
 
	return nRet;
}
#else
int fopen_s_wrp(FILE** const p_fp, const char* const fpath, const char* const mode)
{
	*p_fp = fopen(fpath, mode);
	return (*p_fp == NULL);
}
int sprintf_s_wrp(char buf[], const size_t bufsz, const char* const fmt, ...)
{
	va_list ap;
	int nRet;
 
	va_start(ap, fmt);
	nRet = vsprintf(buf, fmt, ap);
	va_end(ap);
 
	return nRet;
}
#define _countof(arr)	(sizeof(arr) / sizeof(arr[0]))
#endif
 
/// 実部と虚部が交代に並ぶ形式の複素数リストを表示する。
void show_re_im_seq(const std::vector<double>& s, const int p)
{
	const size_t hsz = (size_t)1 << (p - 1);
 
	printf("Re:");
	for (size_t i = 0; i < hsz; i++) {
		printf(" % 12f", s[2 * i]);
	}
	printf("\n");
	printf("Im:");
	for (size_t i = 0; i < hsz; i++) {
		printf(" % 12f", s[2 * i + 1]);
	}
	printf("\n");
}
 
/// 実部と虚部が交代に並ぶ形式の複素数リストを表示する。
void show_re_im_seq(const std::vector<I_TYPE>& s, const int p)
{
	char fmt[128];
	sprintf_s_wrp(fmt, _countof(fmt), "%%0%dlu", FIG);
 
	const size_t hsz = (size_t)1 << (p - 1);
	printf("Re:");
	for (size_t i = 0; i < hsz; i++) {
		printf(fmt, s[2 * i]);
	}
	printf("\n");
	printf("Im:");
	for (size_t i = 0; i < hsz; i++) {
		printf(fmt, s[2 * i + 1]);
	}
	printf("\n");
}
 
namespace priroot
{
	// データの桁数の桁数を表す型
	typedef int expn_t;
 
	// データの桁数を表す型
	typedef int64_t pow_t;
 
#ifdef SHOW_SIN_TABLE
	size_t g_sin_tblent_cnt = 0;
#endif
 
	/// 1の原始n乗根を表す。
	/// nの剰余計算を高速化するため、nは2^pに制限する。
	class basic_nth_root
	{
		/*const*/ expn_t sv_p;
		/*const*/ pow_t t360;
		/*const*/ pow_t m360;
		/*const*/ pow_t t090;
		std::vector<double> m_sin;
 
	public:
		basic_nth_root() : sv_p(0), t360(0), m360(0), t090(0) { }
		basic_nth_root(const expn_t p)
			: sv_p(p), t360((pow_t)1 << p), m360(t360 - 1), t090(t360 / 4), m_sin((size_t)(t360 / 4 + 1))
		{
			if (p >= 2) {
				assert(t360 >= 4);
				t090 = t360 / 4;
				const double k = 0.5 * M_PI;
				for (pow_t i = 1; i < t090; i++) {
					m_sin[i] = sin((k * (double)i) / (double)t090);
				}
#ifdef SHOW_SIN_TABLE
				g_sin_tblent_cnt += t090;
				printf("******* %s: p=%d table made. (+%zu, %zu)\n", __FUNCTION__, p, t090, g_sin_tblent_cnt);
#endif
				m_sin[0] = 0.0;
				m_sin[t090] = 1.0;
			}
		}
 
		expn_t p() const { return sv_p; }
 
		pow_t n() const { return t360; }
 
		/// 1の原始n乗根のk乗を取得する。
		void pow(const pow_t k_, double& re, double& im) const {
			assert(k_ >= 0);
			pow_t k = k_;
			k &= m360;		// nの剰余
			if (sv_p < 2) {
				assert(k == 0 || k == 1);
				im = 0.0;
				re = (k == 0) ? 1.0 : -1.0;
				return;
			}
			assert(0 <= k && k < 4 * t090);
			if (k <= t090) {
				re = m_sin[t090 - k];
				im = m_sin[k];
			}
			else if (k <= 2 * t090) {
				re = -m_sin[k - t090];			// = t090 - (2 * t090 - k)
				im = m_sin[2 * t090 - k];
			}
			else if (k <= 3 * t090) {
				re = -m_sin[3 * t090 - k];		// = t090 - (k - 2 * t090)
				im = -m_sin[k - 2 * t090];
			}
			else {
				re = m_sin[k - 3 * t090];		// = t090 - (4 * t090 - k)
				im = -m_sin[4 * t090 - k];
			}
		}
 
	};
 
	/// 1の原始n乗根を表す。
	class nth_root
	{
		expn_t max_p;
 
		// 1の原始2^p乗根のr乗を収めたテーブルのベクタ
		// basic_tables[p]が1の原始2^p乗根のテーブルを表す。
		std::vector<basic_nth_root> basic_tables;
 
		// 1の原始2^(p+m)乗根のみを収めたベクタ
		// high_order_root_tables[m]が1の原始2^(p+m)乗根の値。(こちらはベクタ要素がテーブルではなく値を表す。)
		std::vector<std::pair<double, double> > high_order_root_values;
 
		/*
			(NOTE)
			1の原始n乗根をw_nと書くことにすると、{ b_n }を0か1からなる数列、rを適当な整数として
			　　k = b_0 + 2 * b_1 + (2^2) * b_2 + ... * (2^(m-1)) * b_(m-1) + { (2^m) * r }
			であるとき、
				(w_(2^(p+m)))^k = w_(2^(p+m))^b_0 * w_(2^(p+(m-1)))^b_1 * w_(2^(p+(m-2))^b_2 * ... * w_(2^(p+1))^b_(m-1) * { w_p^(rの2^pに対する剰余) }
			と書けるので、
				w_p^r (r=0..(2^p-1)) の値
				w_2^(p+q)  (q=1..m) の値
			があれば、(w^(p+m))^k を計算できる。
			前者は任意の指数rについて計算できねばならないため、テーブルで実現する場合はO(2^p)オーダーのメモリを要するが、
			後者はm個の値だけ記憶しておけば良いため、O(m)のオーダーで済む。そのかわりkが与えられる都度値の掛け算が発生する。
		*/
 
	public:
		nth_root() : max_p(0) { }
 
		/// 1の原始2^p乗根のテーブルを用意する。
		void alloc_table(const expn_t p) {
			if (p > max_p) {
				// (テーブル生成済のpより大きいp)
				// まずテーブル生成を検討する。
				if (p <= BASIC_SINTBL_P_MAX) {
					// (pが制限値以下)
					// [max_p+1..p]のテーブルを新規生成
					basic_tables.resize((size_t)(p + 1));
					for (expn_t i = max_p + 1; i <= p; i++) {
						basic_tables[i] = basic_nth_root(i);
					}
					max_p = p;
				}
			}
 
			if (p > max_p) {
				// (任意指数に対するテーブル化が不能な大きさのp)
				// 指数k=1の値のみ記憶する。
				const expn_t m = p - max_p;
				if ((size_t)m >= high_order_root_values.size()) {
					high_order_root_values.resize((size_t)(m + 1));
					std::pair<double, double>& ent = high_order_root_values[m];		// Alias
					const pow_t big_n = (pow_t)1 << p;
					const double arg = (2 * M_PI) / big_n;
					ent.first = cos(arg);		// 実部
					ent.second = sin(arg);		// 虚部
				}
			}
		}
 
		/// 1の原始2^p乗根のk乗を取得する。
		void pow(const expn_t p, const pow_t k, double& re, double& im) const {
			if (p <= max_p) {
				// (w_(2^p))^k算出
				basic_tables[p].pow(k, re, im);
			}
			else {
				const expn_t m = p - max_p;
				const pow_t r = k >> m;
				const pow_t b = k & (((pow_t)1 << m) - 1);
 
				// (w_(2^max_p))^r算出
				basic_tables[max_p].pow(r, re, im);
 
				// w_(2^(max_p + i))を掛け合わせる
				pow_t mask = (pow_t)1 << (m - 1);
				for (expn_t i = 1; i <= m; i++) {
					assert(mask > 0);
					if ((b & mask) != 0) {
						const std::pair<double, double>& ent = high_order_root_values[i];		// Alias
						const double tmp_re = re * ent.first - im * ent.second;
						const double tmp_im = re * ent.second + im * ent.first;
						re = tmp_re;
						im = tmp_im;
					}
					mask >>= 1;
				}
				assert(mask == 0);
			}
		}
 
	};
 
}	// namespace priroot
 
namespace fftn
{
	using namespace priroot;
 
	/// ビット数bitwのBTR演算
	pow_t btr(const pow_t x, const expn_t bitw) {
		pow_t y = 0;
		for (expn_t i = 0; i <= (bitw - 1) / 2; i++) {
			const pow_t b = ((pow_t)1 << i) & x;
			y |= (b << ((bitw - 1) - 2 * i));
		}
		for (expn_t i = (bitw - 1) / 2 + 1; i < bitw; i++) {
			const pow_t b = ((pow_t)1 << i) & x;
			y |= (b >> (2 * i - (bitw - 1)));
		}
		return y;
	}
 
	/// フーリエ変換
	/// DFTの原理式
	///   X(k) = Σ[j=0..t360-1]{ x(j) * w^(j*k) }  (k=0..t360-1)
	/// より
	///   X(k) = Σ[j=0..t180-1]{ x(2*j) * w^(2*j*k) } + Σ[j=0..t180-1]{ x(2*j+1) * w^((2*j+1)*k) }
	///        = Σ[j=0..t180-1]{ x(2*j) * w^(2*j*k) } + w^k * Σ[j=0..t180-1]{ x(2*j+1) * w^(2*j*k) }
	/// さらに、kをk+t180に置き換えると以下が成立する。
	///   X(k+t180) = Σ[j=0..t180-1]{ x(2*j) * w^(2*j*(k + t180) } + w^(k+t180) * Σ[j=0..t180-1]{ x(2*j+1) * w^(2*j*(k+t180) }
	///             = Σ[j=0..t180-1]{ x(2*j) * w^(2*j*k)         } - w^k        * Σ[j=0..t180-1]{ x(2*j+1) * w^(2*j*k) }
	/// よって、
	///   X_even(k) = Σ[j=0..t180-1]{ x(2*j  ) * w^(2*j*k) } (k=0..t180-1)
	///   X_odd(k)  = Σ[j=0..t180-1]{ x(2*j+1) * w^(2*j*k) } (k=0..t180-1)
	/// として、X(k) (k=0..t360)は以下のバタフライ演算で表せる。
	/// 　X(k     ) = X_even(k) + w^k * X_odd(k) (k=0..t180-1)
	///   X(k+t180) = X_even(k) - w^k * X_odd(k) (k=0..t180-1)
	/// これを、大元の時間領域データx(j)の実部がbuf[2*j]、虚部がbuf[2*j + 1]に格納されている前提で行う。
	void fouri(
		std::vector<double>::iterator buf,
		const expn_t p,
		nth_root& w)
	{
		// 再帰終端判定
		if (p == 0) {
			// (要素数2^0のフーリエ変換)
			// 単一要素x(j)のフーリエ変換はx(j)なので何もしない。
			return;
		}
 
		const pow_t t360 = (pow_t)1 << p;
		const pow_t t180 = (pow_t)1 << (p - 1);
 
		w.alloc_table(p);
 
		// X_even(k)取得
		// [0..t180-1]に対し、w^2kを回転因子とするフーリエ変換をin-placeで実行する。
		fouri(buf, p - 1, w);
 
		// X_odd(k)取得
		// [t180..t360-1]に対し、w^2kを回転因子とするフーリエ変換をin-placeで実行する。
		// t180に2を掛けているのは、実部と虚部の2要素セットでt001であることによる。
		fouri(buf + 2 * t180, p - 1, w);
 
		// バタフライ演算
		// X(k     ) = X_even(k) + w^k * X_odd(k)
		// X(k+t180) = X_even(k) - w^k * X_odd(k)
		for (pow_t k = 0; k < t180; k++) {
			const pow_t ofs_even = k << 1;
			const pow_t ofs_odd = (k + t180) << 1;
 
			// X_even(k)
			const double X_even_k_re = buf[ofs_even];
			const double X_even_k_im = buf[ofs_even + 1];
 
			// X_odd(k)
			double X_odd_k_re = buf[ofs_odd];
			double X_odd_k_im = buf[ofs_odd + 1];
 
			// X_odd(k) * w^k 算出、ここでwは1の原始t360乗根
			double wk_re, wk_im;
			w.pow(p, k, wk_re, wk_im);
			const double re = X_odd_k_re * wk_re - X_odd_k_im * wk_im;
			const double im = X_odd_k_re * wk_im + X_odd_k_im * wk_re;
 
			// X(k     ) = X_even(k) + w^k * X_odd(k) = X_even(k) + (re + i * im)
			buf[ofs_even] = X_even_k_re + re;
			buf[ofs_even + 1] = X_even_k_im + im;
 
			// X(k+t180) = X_even(k) - w^k * X_odd(k) = X_even(k) - (re + i * im)
			buf[ofs_odd] = X_even_k_re - re;
			buf[ofs_odd + 1] = X_even_k_im - im;
		}
	}
 
	/// Bit reverse orderにin-placeで並べ替える。
	void sort_by_btr(
		std::vector<double>::iterator buf,
		const expn_t p)
	{
		const pow_t t360 = (pow_t)1 << p;
 
		for (pow_t i = 0; i < t360; i++) {
			const pow_t btr_i = btr(i, p);
 
			// (btr_i, i)と(i, btr_i)の両方についてswapすると元に戻ってしまうので、
			// 片方のみswap対象とする。
			if (btr_i < i) {
				std::swap(buf[2 * btr_i], buf[2 * i]);				// 実部
				std::swap(buf[2 * btr_i + 1], buf[2 * i + 1]);		// 虚部
			}
		}
	}
 
	/// 逆フーリエ変換
	/// フーリエ変換とは逆の以下のバタフライ演算を行う。
	/// 　x(k     ) = (x_even(k) + w^(-k) * x_odd(k)) / t360 (k=0..t180-1)
	///   x(k+t180) = (x_even(k) - w^(-k) * x_odd(k)) / t360 (k=0..t180-1)
	/// これを、大元の周波数領域データX(k)の実部がbuf[2*k]、虚部がbuf[2*k+1]に格納されている前提で行う。
	void fouriinv(
		std::vector<double>::iterator buf,
		const expn_t p,
		nth_root& w)
	{
		// 再帰終端判定
		if (p == 0) {
			// (要素数2^0のフーリエ変換)
			// 単一要素x(j)のフーリエ変換はx(j)なので何もしない。
			return;
		}
 
		const pow_t t360 = (pow_t)1 << p;
		const pow_t t180 = (pow_t)1 << (p - 1);
 
		w.alloc_table(p);
 
		// x_even(k)取得
		// [0..t180-1]に対し、w^2kを回転因子とするフーリエ変換をin-placeで実行する。
		fouriinv(buf, p - 1, w);
 
		// x_odd(k)取得
		// [t180..t360-1]に対し、w^2kを回転因子とするフーリエ変換をin-placeで実行する。
		// t180に2を掛けているのは、実部と虚部の2要素セットでt001であることによる。
		fouriinv(buf + 2 * t180, p - 1, w);
 
		// バタフライ演算
		// x(k     ) = x_even(k) + w^k * x_odd(k)
		// x(k+t180) = x_even(k) - w^k * x_odd(k)
		for (pow_t k = 0; k < t180; k++) {
			const pow_t ofs_even = k << 1;
			const pow_t ofs_odd = (k + t180) << 1;
 
			// x_even(k)
			const double x_even_k_re = buf[ofs_even];
			const double x_even_k_im = buf[ofs_even + 1];
 
			// x_odd(k)
			double x_odd_k_re = buf[ofs_odd];
			double x_odd_k_im = buf[ofs_odd + 1];
 
			// x_odd(k) * w^(-k) 算出、ここでwは1の原始t360乗根
			double wk_re, wk_im;
			w.pow(p, k, wk_re, wk_im);
			const double re = x_odd_k_re * wk_re + x_odd_k_im * wk_im;
			const double im = x_odd_k_im * wk_re - x_odd_k_re * wk_im;
 
			// X(k     ) = x_even(k) + w^k * x_odd(k) = x_even(k) + (re + i * im)
			buf[ofs_even] = (x_even_k_re + re) / 2.0;
			buf[ofs_even + 1] = (x_even_k_im + im) / 2.0;
 
			// X(k+t180) = x_even(k) - w^k * x_odd(k) = x_even(k) - (re + i * im)
			buf[ofs_odd] = (x_even_k_re - re) / 2.0;
			buf[ofs_odd + 1] = (x_even_k_im - im) / 2.0;
		}
	}
 
}	// namespace fftn
 
// ブロックSix-Step FFTアルゴリズム
// https://w...content-available-to-author-only...c.jp/public/VOL9/special/7.pdf
// のC++実装
// 実装の都合により、行数n1、列数n2、ブロックの行数nbは2の冪に制限する。
// また、PCスタンドアロン実行用に行列転置処理を簡素化している。
namespace fftb6
{
	using namespace priroot;
 
	/// 最適な行数(2の冪)の指数を返す。
	expn_t get_best_expn_n1(const expn_t p)
	{
		const expn_t exp_expn_n1 = (p + 1) / 2;
		return std::min(exp_expn_n1, EXPN_CAPACITY);
	}
 
	/// 最適なブロックサイズ(2の冪)の指数を返す。
	expn_t get_best_expn_nb(const expn_t expn_n)
	{
		return std::min(expn_n, (EXPN_CAPACITY > expn_n) ? EXPN_CAPACITY - expn_n : 0);
	}
 
	/// 転置処理
	/// 転置元配列src[]は (2^expn_n1)行(2^(p-expn_n1))列の2次元配列
	/// 転置先配列dst[]は (2^(p-expn_n1))行(2^expn_n1)列の2次元配列
	/// とそれぞれ解釈する。
	void transpose(
		std::vector<double>::const_iterator src,
		std::vector<double>::iterator dst,
		const expn_t p,
		const expn_t expn_n1)
	{
		const expn_t expn_n2 = p - expn_n1;
 
		const pow_t t360 = (pow_t)1 << p;
		const pow_t n1 = (pow_t)1 << expn_n1;
		const pow_t n2 = (pow_t)1 << expn_n2;
 
		// ストレートな転置アルゴリズム
		// 正方行列の転置への分解はPCスタンドアロン実行に向かないため行わない。
#pragma omp parallel for
		for (pow_t i = 0; i < n1; i++) {
			for (pow_t j = 0; j < n2; j++) {
				const pow_t src_idx = n2 * i + j;
				const pow_t dst_idx = n1 * j + i;
 
				dst[2 * dst_idx] = src[2 * src_idx];				// 実部
				dst[2 * dst_idx + 1] = src[2 * src_idx + 1];		// 虚部
			}
		}
	}
 
	// 前方宣言
	void fouri_wrp(
		std::vector<double>::iterator buf,
		const expn_t p,
		nth_root& w);
	void fouriinv_wrp(
		std::vector<double>::iterator buf,
		const expn_t p,
		nth_root& w);
 
	/// フーリエ変換
	void fourib6(
		std::vector<double>::iterator buf,
		const expn_t p,
		nth_root& w,
		const expn_t expn_n1)
	{
		// 行数が全体のサイズ以下であること
		if (!(0 <= expn_n1 && expn_n1 <= p)) {
			// ここに来たら呼び出し元のバグ
			abort();
		}
 
		// 列数(2の冪)の指数
		const expn_t expn_n2 = p - expn_n1;
 
		// ブロックサイズ
		const expn_t expn_nb = get_best_expn_nb(expn_n2);
 
		// buf[0..t360-1]を複素数を要素とする2次元配列とみなす。
		// 入力に関しては j=n2*j1 + j2 (0≦j2＜n2) として、buf[j1, j2] (n1行n2列)
		// 出力に関しては k=n1*k2 + k1 (0≦k1＜n1) として、buf[k1, k2] (n1行n2列)
		// 出力の順序とメモリのアドレス順を合わせるには、buf[k1, k2]を転置してn2行n1列にする必要がある。
		const pow_t t360 = (pow_t)1 << p;
		const pow_t n1 = (pow_t)1 << expn_n1;
		const pow_t n2 = (pow_t)1 << expn_n2;
		const pow_t nb = (pow_t)1 << expn_nb;
 
		// SINテーブル獲得
		// ここで指数pのテーブルを確保しておくことで、
		// マルチスレッド処理中にテーブルのstd::vector::realloc()が呼ばれなくして
		// 排他制御を省略できる。
		w.alloc_table(p);
 
		// 6 step algorithm
#pragma omp parallel for
		for (pow_t JJ = 0; JJ < n2; JJ += nb) {
			// 作業バッファ準備
			// 2を掛けているのは、実部と虚部の2要素セット1要素であることによる。
			// スレッド毎に確保する必要があるため、parallel for対象ブロック内で実施する。
			std::vector<double> work((size_t)(2 * nb * n1));
 
			// ストレートな転置アルゴリズム
			// 正方行列の転置への分解はPCスタンドアロン実行に向かないため行わない。
			for (pow_t j = JJ; j < JJ + nb; j++) {
				for (pow_t i = 0; i < n1; i++) {
					// ここでのi、jはj1、j2にあたる。
					// 直下の処理は転置処理
					//   work[j2 - JJ, j1] = buf[j1, j2]
					// にあたる。
					const pow_t src_idx = n2 * i + j;
					const pow_t dst_idx = n1 * (j - JJ) + i;
					work[2 * dst_idx] = buf[2 * src_idx];				// 実部
					work[2 * dst_idx + 1] = buf[2 * src_idx + 1];		// 虚部
				}
			}
 
			// Step 2: nb組のn1点multi row FFT
			for (pow_t i = 0; i < nb; i++) {
				// ここでのiはj2-JJに対応する。
				// 直下の処理はwork[j2 - JJ, j1]のj1に関するフーリエ変換
				//   work[j2 - JJ, k1] = Σ[j1=0..n1-1]{ work[j2 - JJ, j1] * (w_n1)^(j1 * k1) }
				//                     = Σ[j1=0..n1-1]{ buf[j1, j2] * (w_n1)^(j1 * k1) }
				// にあたる。ここで、w_n1は1の原始n1乗根。
				const pow_t row_head = 2 * n1 * i;
				fouri_wrp(work.begin() + row_head, expn_n1, w);
			}
 
			// Step 3: ひねり係数をかける
			// Step 4: 転置
			for (pow_t j = JJ; j < JJ + nb; j++) {
				for (pow_t i = 0; i < n1; i++) {
					// ここでのi、jはk1、j2にあたる。
 
					// 転置のsrcとdst
					const pow_t src_idx = n1 * (j - JJ) + i;	// n1 * (j2 - JJ) + k1
					const pow_t dst_idx = n2 * i + j;			// n2 * k1 + j2
 
					// ひねり係数(w_n)^(j2*k1)
					// ここで、w_nは1の原始n乗根。
					double omg_re, omg_im;
					w.pow(p, j * i, omg_re, omg_im);
 
					// ひねり係数を掛けて転置
					// 直下の処理は、ひねり係数を掛けて転置する処理
					//   buf[k1, j2] = work[j2 - JJ, k1] * (w_n)^(j2*k1)
					// にあたる。
					const double src_re = work[2 * src_idx];
					const double src_im = work[2 * src_idx + 1];
					buf[2 * dst_idx] = src_re * omg_re - src_im * omg_im;			// 実部
					buf[2 * dst_idx + 1] = src_im * omg_re + src_re * omg_im;		// 虚部
				}
			}
		}
 
		// Setp 5: N1組のN2点multi row FFT
		// ブロックSix-step algorithmの引用元コードによれば
		// nb組のn2点multi row FFTに区分して行うべきところだが、
		// PCスタンドアロン実行に向かないため区分しない。
#pragma omp parallel for
		for (pow_t i = 0; i < n1; i++) {
			// ここでのiはk1にあたる。
			// 直下の処理は、buf[k1, j2]のj2に関するフーリエ変換
			//   buf[k1, k2] = Σ[j2=0..n2-1]{ buf[k1, j2] * (w_n2)^(j2 * k2) }
			// にあたる。ここで、w_n2は1の原始n2乗根。
			const pow_t row_head = 2 * n2 * i;
			fouri_wrp(buf + row_head, expn_n2, w);
 
			// Step 6: 転置
			// 本来はフーリエ変換結果X(k)がメモリ上で並ぶようにbuf[k1, k2]をn2行×n1列の2次元配列dst[,]に転置する工程だが、
			// buf[N2 * i + j] を X(N1 * j + i)と解釈することにして省略する。
		}
	}
 
	/// フーリエ逆変換
	/// buf[]としては、fourib6()の結果を転置せずにそのまま与える前提。
	/// expn_n1もfourib6()に与えたものと同じ値を与える。
	void fourib6inv(
		std::vector<double>::iterator buf,
		const expn_t p,
		nth_root& w,
		const expn_t expn_n1)
	{
		// 行数が全体のサイズ以下であること
		if (!(0 <= expn_n1 && expn_n1 <= p)) {
			// ここに来たら呼び出し元のバグ
			abort();
		}
 
		// 列数(2の冪)の指数
		const expn_t expn_n2 = p - expn_n1;
 
		// ブロックサイズ
		const expn_t expn_nb = get_best_expn_nb(expn_n2);
 
		// buf[0..t360-1]を複素数を要素とする2次元配列とみなす。
		// 入力に関しては k=n1*k2 + k1 (0≦k1＜n1) として、buf[k1, k2] (n1行n2列)
		// 出力に関しては j=n2*j1 + j2 (0≦j2＜n2) として、buf[j1, j2] (n1行n2列)
		// 入力の順序とメモリのアドレス順を合わせるには、buf[k1, k2]を転置してn2行n1列にする必要があるが
		// 当関数ではその転置を行わずに済ませる。
		// 出力の順序とメモリのアドレス順は一致する。
		const pow_t t360 = (pow_t)1 << p;
		const pow_t n1 = (pow_t)1 << expn_n1;
		const pow_t n2 = (pow_t)1 << expn_n2;
		const pow_t nb = (pow_t)1 << expn_nb;
 
		// SINテーブル獲得
		// ここで指数pのテーブルを確保しておくことで、
		// マルチスレッド処理中にテーブルのstd::vector::realloc()が呼ばれなくして
		// 排他制御を省略できる。
		w.alloc_table(p);
 
		// Modified 6 step algorithm
		// Setp 1: n1組のn2点multi row IFFT
		// ブロックSix-step algorithmの引用元コードによれば
		// nb組のn2点multi row FFTに区分して行うべきところだが、
		// PCスタンドアロン実行に向かないため区分しない。
#pragma omp parallel for
		for (pow_t i = 0; i < n1; i++) {
			// ここでのiはk1にあたる。
			// 直下の処理はbuf[k1, k2]のk2に関する逆フーリエ変換
			//   buf[k1, j2] = (1/n2) * Σ[k2=0..n2-1]{ buf[k1, k2] * (w_n2)^(-(j2 * k2)) }
			// にあたる。ここで、w_n2は1の原始n2乗根。
			const pow_t row_head = 2 * n2 * i;
			fouriinv_wrp(buf + row_head, expn_n2, w);
		}
 
		// Step 3: ひねり係数をかける
		// Step 4: 転置
#pragma omp parallel for
		for (pow_t JJ = 0; JJ < n2; JJ += nb) {
			// 作業バッファ準備
			// 2を掛けているのは、実部と虚部の2要素セット1要素であることによる。
			std::vector<double> work((size_t)(2 * nb * n1));
 
			// ストレートな転置アルゴリズム
			// 正方行列の転置への分解はPCスタンドアロン実行に向かないため行わない。
			for (pow_t j = JJ; j < JJ + nb; j++) {
				for (pow_t i = 0; i < n1; i++) {
					// ここでのi、jはk1、j2にあたる。
 
					// 転置のsrcとdst
					const pow_t src_idx = n2 * i + j;
					const pow_t dst_idx = n1 * (j - JJ) + i;
 
					// ひねり係数の逆数(w_n)^(j2*k1)
					// ここで、w_nは1の原始n乗根。
					double omg_re, omg_im;
					w.pow(p, j * i, omg_re, omg_im);
 
					// ひねり係数を掛けて転置
					// 直下の処理は
					//   work[j2 - JJ, k1] = buf[k1, j2] * (w_n)^(-(j2*k1))
					// にあたる。
					const double src_re = buf[2 * src_idx];
					const double src_im = buf[2 * src_idx + 1];
					work[2 * dst_idx] = src_re * omg_re + src_im * omg_im;			// 実部
					work[2 * dst_idx + 1] = src_im * omg_re - src_re * omg_im;		// 虚部
				}
			}
 
			// nb組のn1点multi row IFFT
			for (pow_t i = 0; i < nb; i++) {
				// ここでのiはj2-JJにあたる。
				// 直下の処理は、work[j2 - JJ, k1]のk1に関する逆フーリエ変換
				//   work[j2 - JJ, j2] = (1/n1) * Σ[k1=0..n1-1]{ work[j2 - JJ, k1] * (w_n1)^(j1 * k1) }
				//                     = (1/n1) * Σ[k1=0..n1-1]{ buf[k1, j2] * (w_n1)^(j1 * k1) }
				// にあたる。ここで、w_n1は1の原始n1乗根。
				const pow_t row_head = 2 * n1 * i;
				fouriinv_wrp(work.begin() + row_head, expn_n1, w);
			}
 
			// IFFT結果をbuf[]の元の場所に書き戻す
			// ストレートな転置アルゴリズム
			// 正方行列の転置への分解はPCスタンドアロン実行に向かないため行わない。
			for (pow_t j = JJ; j < JJ + nb; j++) {
				for (pow_t i = 0; i < n1; i++) {
					// ここでのi、jはj1、j2にあたる。
					// 直下の処理は、転置処理
					//   buf[j1, j2] = work[j2 - JJ, j1]
					// にあたる。
					const pow_t src_idx = n1 * (j - JJ) + i;
					const pow_t dst_idx = n2 * i + j;
					buf[2 * dst_idx] = work[2 * src_idx];				// 実部
					buf[2 * dst_idx + 1] = work[2 * src_idx + 1];		// 虚部
				}
			}
		}
	}
 
	/// フーリエ変換のwrapper
	void fouri_wrp(
		std::vector<double>::iterator buf,
		const expn_t p,
		nth_root& w)
	{
		if (p <= EXPN_CAPACITY) {
			// (FFT結果がL2キャッシュサイズの半分に収まる)
			// ストレートにfftする。
			fftn::sort_by_btr(buf, p);
			fftn::fouri(buf, p, w);
		}
		else {
			// (FFT結果がL2キャッシュサイズの半分に収まならい)
			// Blocked 6 step algorithmでFFTする
			// n1 = √(2^p)が最も効率が良いのでEXPN_CACACITYを超えない範囲で近い値にする。
			// (2^p)/n1がEXPN_CAPACITYを超える場合は、foourib6()から当関数にさらに再帰して細分化する。
			const int n1 = std::min((p + 1) / 2 + 1, EXPN_CAPACITY);
			// フーリエ変換
			fourib6(buf, p, w, n1);
			// 転置
			const pow_t t360 = (pow_t)1 << p;
			std::vector<double> tmp(buf, buf + 2 * t360);
			transpose(tmp.begin(), buf, p, n1);
		}
	}
 
	/// 逆フーリエ変換のwrapper
	void fouriinv_wrp(
		std::vector<double>::iterator buf,
		const expn_t p,
		nth_root& w)
	{
		if (p <= EXPN_CAPACITY) {
			// (IFFT結果がL2キャッシュサイズの半分に収まる)
			// ストレートにifftする。
			fftn::sort_by_btr(buf, p);
			fftn::fouriinv(buf, p, w);
		}
		else {
			// (IFFT結果がL2キャッシュサイズの半分に収まならい)
			// Blocked 6 step algorithmでFFTする
			// n1 = √(2^p)が最も効率が良いのでEXPN_CACACITYを超えない範囲で近い値にする。
			// (2^p)/n1がEXPN_CAPACITYを超える場合は、foourib6()から当関数にさらに再帰して細分化する。
			const int n1 = std::min((p + 1) / 2 + 1, EXPN_CAPACITY);
			const pow_t t360 = (pow_t)1 << p;
			// 転置
			std::vector<double> tmp(buf, buf + (size_t)(2 * t360));
			transpose(tmp.begin(), buf, p, n1);
			// 逆フーリエ変換
			fourib6inv(buf, p, w, p - n1);
		}
	}
 
}	// namespace fftb6
 
namespace fftb6_4n
{
	using namespace priroot;
 
	/// 4n乗根によるフーリエ変換(Blocked 6-step algorithm版)
	/// x(j) (j=0..(2*t360)-1)から
	///   x'(j) = (x(j) + i * x(j+t360)) * u^(j/4) (j=0..t360-1)
	/// を構成し、x'(j)をDFTする。ここで、uは1の原始(4 * mag * t360)乗根 (mag ≧ 1)。
	void fourib6_4n(
		std::vector<double>::iterator buf,
		const expn_t p,
		nth_root& w,
		const expn_t expn_n1)
	{
		const pow_t t360 = (pow_t)1 << p;
 
		w.alloc_table(p + 2);
 
		// { x'(j) }構成
		// { x(j) + i * x(j+t360) } にu^(j/4)を掛ける。
		const expn_t p2 = p + 2;
		for (pow_t j = 0; j < t360; j++) {
			const double a = buf[2 * j];
			const double b = buf[2 * j + 1];
 
			// u = w^4としてu^(j/4) = w^(j)
			double wj_re, wj_im;
			w.pow(p2, j, wj_re, wj_im);
			buf[2 * j] = a * wj_re - b * wj_im;
			buf[2 * j + 1] = a * wj_im + b * wj_re;
		}
 
		// フーリエ変換
		fftb6::fourib6(buf, p, w, expn_n1);
	}
 
	/// 4n乗根による逆フーリエ変換(Blocked 6-step algorithm版)
	void fourib6_4ninv(
		std::vector<double>::iterator buf,
		const expn_t p,
		nth_root& w,
		const expn_t expn_n1)
	{
		const pow_t t360 = (pow_t)1 << p;
 
		w.alloc_table(p + 2);
 
		// 逆フーリエ変換
		fftb6::fourib6inv(buf, p, w, expn_n1);
 
		// { x(j) }復元
		const expn_t p2 = p + 2;
		for (pow_t j = 0; j < t360; j++) {
			const double a = buf[2 * j];
			const double b = buf[2 * j + 1];
 
			// u = w^4としてu^(-j/4) = w^(-j)を掛ける
			double wj_re, wj_im;
			w.pow(p2, j, wj_re, wj_im);
			buf[2 * j] = a * wj_re + b * wj_im;
			buf[2 * j + 1] = b * wj_re - a * wj_im;
		}
	}
 
}	// namespace fft4n
 
namespace oper
{
	using namespace fftb6_4n;
 
	struct I
	{
		std::vector<I_TYPE> data;	// 基数RADIXの多倍長データ
		size_t ndigits;				// dataに入っている有効な桁数
 
		I(const size_t cap)
			: data(cap), ndigits((size_t)0)
		{
			/*pass*/
		}
	};
 
	struct F
	{
		std::vector<double> data;	// 基数[-(RADIX/2), RADIX/2)の多倍長データ
		int p;						// 2^p == (dataの要素数) となるp
 
		F(const int p_)
			: data((size_t)1 << p_), p(0)
		{
			/*pass*/
		}
	};
 
	/// 整数のフーリエ変換
	void i2f(F& a, const I& b, const int p, priroot::nth_root& w)
	{
		size_t i;
 
		// 次数2^(p-1) = t360の4n乗根フーリエ変換を行う。
		// 結果は実部と虚部を合わせて2^p = (2 * t360)桁分となる。
		const pow_t t360 = (pow_t)1 << (p - 1);
 
		assert(b.ndigits <= (size_t)t360);
		assert((size_t)(2 * t360) <= a.data.size());
 
#ifdef SHOW_I
		printf("%s: Before pre tr.:\n", __FUNCTION__);
		show_re_im_seq(b.data, p);
#endif
 
		// フーリエ変換の前処理
		// (bが表す整数) = Σ[i=0..a.ndigits-1]{ b.data[i] * RADIX^i } (0≦b.data[i]＜RADIX)
		// を、
		// (aが表す整数) = Σ[i=0..a.ndigits-1]{ a.data[i] * RADIX^i } (-RADIX / 2≦a.data[i]＜RADIX / 2)
		// に変換する。(a, bが同じ整数を表すように桁上げも行う。)
		a.p = p;
		int carry = 0;
		for (i = 0; i < b.ndigits - 1; i++) {
			// 実部虚部隣接化
			// b.data[t360..]を虚部に配置する。
			const size_t dst_i = (i < (size_t)t360) ? 2 * i : 2 * (i - (size_t)t360) + 1;
 
			const int32_t t = b.data[i] + carry;	// 桁[i]の値
			if (t < (int32_t)RADIX / 2) {
				// (桁[i]の値∈[0, RADIX / 2) )
				// 何もしない
				a.data[dst_i] = t;
				carry = 0;
			}
			else {
				// (桁[i]の値∈[RADIX / 2, RADIX) )
				// 補正実施
				// まず桁[i] -= RADIX により桁[i]の値∈[0, RADIX / 2)とする。ただし
				// それだけでは(aが表す整数)が RADIX * RADIX^i = RADIX^(i+1)だけ減ってしまうので、
				// 減った分をcarryで一つ上の桁に回して補填する。
				a.data[dst_i] = (double)(t - (int32_t)RADIX);
				carry = 1;
			}
		}
		{
			// 実部虚部隣接化
			const size_t dst_i = (i < (size_t)t360) ? 2 * i : 2 * (i - (size_t)t360) + 1;
 
			// 最上位桁
			a.data[dst_i] = (double)(b.data[i] + (I_TYPE)carry);
			i++;
		}
		for (; i < (size_t)(2 * t360); i++) {
			// 実部虚部隣接化
			const size_t dst_i = (i < (size_t)t360) ? 2 * i : 2 * (i - (size_t)t360) + 1;
 
			a.data[dst_i] = 0.0;
		}
 
#if defined(SHOW_ITM) || defined(SHOW_I)
		printf("Before fouri4n():\n");
		show_re_im_seq(a.data, a.p);
#endif
 
		const expn_t expn_n2 = (p - 1) / 2;
		const expn_t expn_n1 = (p - 1) - expn_n2;
 
		// フーリエ変換実施
		fftb6_4n::fourib6_4n(a.data.begin(), p - 1, w, expn_n1);
 
#ifdef SHOW_ITM
		printf("After fouri4n():\n");
		show_re_im_seq(a.data, a.p);
#endif
	}
 
	/// 整数のフーリエ変換結果の積(結果は整数)
	void mul_f2i(I& a, const F& b, const F& c, F& d, double& err_max, priroot::nth_root& w) {
		int64_t carry;
		size_t i, t;
 
		const int p = b.p;
 
		// 次数2^(p-1) = t360の4n乗根フーリエ変換結果の積を逆フーリエ変換する。
		// 結果は実部と虚部を合わせて2^p = (2 * t360)桁となる。
		const pow_t t360 = (size_t)1 << (p - 1);
 
		assert(p == c.p);
		assert((size_t)(2 * t360) <= d.data.size());
 
		// 積
		for (i = 0; i < (size_t)t360; i++) {
			const double b_i_re = b.data[2 * i];
			const double b_i_im = b.data[2 * i + 1];
			const double c_i_re = c.data[2 * i];
			const double c_i_im = c.data[2 * i + 1];
 
			// d[i] = b[i] * c[i]
			const double d_i_re = b_i_re * c_i_re - b_i_im * c_i_im;
			const double d_i_im = b_i_re * c_i_im + b_i_im * c_i_re;
			d.data[2 * i] = d_i_re;
			d.data[2 * i + 1] = d_i_im;
		}
 
#ifdef SHOW_ITM
		printf("Before fouri4ninv():\n");
		show_re_im_seq(d.data, d.p);
#endif
 
		const expn_t expn_n2 = (p - 1) / 2;
		const expn_t expn_n1 = (p - 1) - expn_n2;
 
		// 逆フーリエ変換
		fftb6_4n::fourib6_4ninv(d.data.begin(), p - 1, w, expn_n1);
 
#ifdef SHOW_ITM
		printf("After fouri4ninv():\n");
		show_re_im_seq(d.data, d.p);
#endif
 
		const size_t s = std::min(a.data.size(), (size_t)(2 * t360));
 
		// Carry and fix処理
		// ただし対象とする桁の並びd.data[]は、
		// 桁の値が[0, RADIX)ではなく、[-RADIX / 2, RADIX / 2)である。
		carry = 0;
		t = 1;
		//const double k = ldexp(1.0, -p + 1);		// k = 1.0 * 2^(-p + 1)
		double k = 1.0;		// fouri4ninv()結果は2^pで割る必要無し。
		for (i = 0; i < s; i++) {
			// 実部虚部隣接化解除
			// b.data[t360..]を虚部に配置する。
			const size_t src_i = (i < (size_t)t360) ? 2 * i : 2 * (i - (size_t)t360) + 1;
			//printf("t360=%lld, s=%zu, i=%zu, src_i=%zu\n", t360, s, i, src_i);
 
			const double x = d.data[src_i] * k;
			int64_t e = (int64_t)floor(x + 0.5);
			err_max = std::max(err_max, fabs(x - e));
			e += carry;
			carry = e / RADIX;
			int64_t f = e - carry * RADIX;
			if (f < 0) {
				f += RADIX;
				carry--;
			}
			a.data[i] = (I_TYPE)f;
			if (f != 0) {
				t = i + 1;
			}
		}
		a.ndigits = t;
		if (carry != 0) {
			if (a.ndigits < a.data.size()) {
				assert(0 <= carry && carry < RADIX);
				a.data[a.ndigits++] = (I_TYPE)carry;
			}
			else {
				// ここに来たら桁あふれ
				abort();
			}
		}
		for (; i < s; i++) {
			// 実部虚部隣接化解除
			const size_t src_i = (i < (size_t)t360) ? 2 * i : 2 * i + 1;
 
			const double x = d.data[src_i] * k;
			const int64_t e = (int64_t)floor(x + 0.5);
			err_max = std::max(err_max, fabs(x - e));
			assert(e == 0);
		}
	}
 
	/// 整数の和
	void add_i(I& a, const I& b_, const I& c_) {
		I_TYPE carry, d;
		size_t i;
 
		const I& b = (b_.ndigits > c_.ndigits) ? c_ : b_;	// Alias
		const I& c = (b_.ndigits > c_.ndigits) ? b_ : c_;	// Alias
		assert(b.ndigits <= c.ndigits);
		assert(c.ndigits <= a.data.size());
 
		carry = 0;
		for (i = 0; i < b.ndigits; i++) {
			d = b.data[i] + c.data[i] + carry;
			carry = 0;
			if (d >= RADIX) {
				d -= RADIX;
				carry++;
			}
			a.data[i] = d;
		}
		for (; i < c.ndigits; i++) {
			d = c.data[i] + carry;
			carry = 0;
			if (d >= RADIX) {
				d -= RADIX;
				carry++;
			}
			a.data[i] = d;
		}
		a.ndigits = c.ndigits;
		if (a.ndigits < a.data.size()) {
			if (carry != 0) {
				a.data[a.ndigits++] = carry;
			}
		}
		else {
			if (carry != 0) {
				// ここに来たら桁あふれ
				abort();
			}
		}
	}
 
	/// 整数のファイル出力
	void print(const char* const filename, const I& a)
	{
		char format[10];
		int nRet;
 
		assert(a.data.size() > (size_t)0);
		assert(a.ndigits <= a.data.size());
 
		FILE* fp;
		nRet = fopen_s_wrp(&fp, filename, "w");
		if (nRet != 0) {
			fflush(stdout);
			fprintf(stderr, "ERROR: fopen_s_wrp() failed. (nRet=%d)\n", nRet);
			abort();
		}
 
		sprintf_s_wrp(format, _countof(format), "%%0%du", FIG);
 
		size_t s = a.ndigits;
		fprintf(fp, "%lu", (unsigned long)a.data[--s]);
		while (s != 0) {
			fprintf(fp, format, a.data[--s]);
		}
		fclose(fp);
	}
 
}	// namespace oper
 
namespace
{
	// N ≧ log2(s1 * s2)を満たす最小のNを求める。
	int s2p(const size_t s1, const size_t s2) {
		int i;
		for (i = 1; i < 64; i++) {
			if (((size_t)1 << i) + 1 >= s1 + s2) {
				// (2^i + 1 ≧ (s1の有効桁数) + (s2の有効桁数))
				break;
			}
		}
		return i;
	}
 
}	// namespace
 
int main()
{
	using namespace oper;
 
	const int n = 34;
 
	nth_root w;
 
	const int max_p = s2p(((size_t)((1LLU << n) * log10(2)) / FIG + 1), 1);
	const size_t cap = (size_t)1 << max_p;
 
	I a(cap);
	F x(max_p);
 
	a.data[0] = 1;
	a.ndigits = 1;
 
	double err_max = 0.0;
#ifdef SHOW_CSM_TIME
	std::vector<double> csm_time;
	const double startTmg_0 = omp_get_wtime();
#endif
	for (int i = 0; i < n; i++) {
#ifdef SHOW_CSM_TIME
		const double startTmg = omp_get_wtime();
#endif
 
		// 多倍長整数xのフーリエ変換
		// p ≧ log2(a * a)を満たす最小のpを求め、
		// aの次数2^pのフーリエ変換結果をxに格納する。
		const int p = s2p(a.ndigits, a.ndigits);
		i2f(x, a, p, w);
 
		// x = x*x、および結果のxを整数に戻してaに格納する
		mul_f2i(a, x, x, x, err_max, w);
		add_i(a, a, a);
 
#ifdef SHOW_CSM_TIME
		const double endTmg = omp_get_wtime();
		csm_time.push_back(endTmg - startTmg);
#endif
 
		// 途中経過出力
#ifdef SAVE_ITM_RESULT
		/*pass*/
#else
		if (i >= n - 1)
#endif
		{
			char filename[200];
			sprintf_s_wrp(filename, _countof(filename), "%d.txt", i + 1);
			print(filename, a);
		}
		printf("%d %f\n", i + 1, err_max);
	}
#ifdef SHOW_CSM_TIME
	const double endTmg_0 = omp_get_wtime();
	printf("Total with file write = %10f sec\n", endTmg_0 - startTmg_0);
	printf("Total only core time  = %10f sec\n", std::accumulate(csm_time.begin(), csm_time.end(), 0.0));
	for (size_t i = 0; i < csm_time.size(); i++) {
		printf("2^2^(%2zu) %10f sec\n", i + 1, csm_time[i]);
	}
#endif
 
	return 0;
}
 

Ly8gMl4oMl4zNCAtIDEpID0gMl4xNzE3OTg2OTE4MyDjgpLoqIjnrpfjgZnjgovjgIIKI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0ZGludC5oPgojZGVmaW5lIF9VU0VfTUFUSF9ERUZJTkVTCiNpbmNsdWRlIDxtYXRoLmg+CiNpbmNsdWRlIDxhc3NlcnQuaD4KI2luY2x1ZGUgPHN0ZGFyZy5oPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8dXRpbGl0eT4KI2luY2x1ZGUgPG51bWVyaWM+CgojaW5jbHVkZSA8b21wLmg+CgovLyBbREJHU1ddIOS4remWk+e1kOaenOihqOekugovLyNkZWZpbmUgU0hPV19JVE0KCi8vIFtEQkdTV10gSeihqOekugovLyNkZWZpbmUgU0hPV19JCgovLyBbREJHU1ddIFNJTl9UQUJMReS9nOaIkOeKtuazgeihqOekugovLyNkZWZpbmUgU0hPV19TSU5fVEFCTEUKCi8vIFtEQkdTV10g5raI6LK75pmC6ZaT6KGo56S6CiNkZWZpbmUgU0hPV19DU01fVElNRQoKLy8gW0RCR1NXXSDoqIjnrpfpgJTkuK3ntZDmnpzjga7kv53lrZgKLy8jZGVmaW5lIFNBVkVfSVRNX1JFU1VMVAoKdHlwZWRlZiB1aW50MzJfdCBJX1RZUEU7CgovLyBbQ09ORl0g5Z+65pysU0lO44OG44O844OW44Or44Gu5pyA5aSn6KaB57Sg5pWwCiNkZWZpbmUgQkFTSUNfU0lOVEJMX1BfTUFYCQkyOQoKLy8gW0NPTkZdIOWkmuWAjemVt+ODkOODg+ODleOCoTHopoHntKDjga4xMOmAsuaVsOOBp+OBruahgeaVsApjb25zdCBpbnQgRklHID0gNTsKCi8vIFtDT05GXSAxMF5GSUcKY29uc3QgSV9UWVBFIFJBRElYID0gMTAwMDAwOwoKLy8gW0NPTkZdIOS9v+eUqOOBmeOCi0NQVeOBrkwy44Kt44Oj44OD44K344Ol44K144Kk44K6KDLjga7lhqogQnl0ZS/jgrPjgqIp44Gu5oyH5pWwCiNpZmRlZiBOREVCVUcKI2RlZmluZSBFWFBOX0wyQ0hBQ0hFX1NaCQkJMTgJCQkvKiAyNTYgS0IgKi8KI2Vsc2UKI2RlZmluZSBFWFBOX0wyQ0hBQ0hFX1NaCQkJOAkJCS8qIDI1NiBCeXRlIChERUJVRykgKi8KI2VuZGlmCgovLyBbQ09ORl0g5ZCM5LiATDLjgq3jg6Pjg4Pjgrfjg6XjgpLlhbHnlKjjgZnjgovjgrnjg6zjg4Pjg4njga7mlbAoMuOBruWGqinjga7mjIfmlbAKLy8gQ29yZSBpNyAoSFTmnInjgoop44Gn44GvMeOAgUNvcmUgaTUgKEhU54Sh44GXKeOBp+OBrzAKI2RlZmluZSBFWFBOX0wyX1NIQVJJTkdfVEhSRUFEUwkJMQoKLy8gW0NPTkZdIHNpemVvZijopIfntKDmlbApICgy44Gu5YaqKeOBruaMh+aVsChkb3VibGUgMuWAi+OBpzE2IEJ5dGUpCiNkZWZpbmUgRVhQTl9TSVpFT0ZfQ09NUExFWAkJCTQKCnN0YXRpY19hc3NlcnQoKHNpemVfdCkxIDw8IEVYUE5fU0laRU9GX0NPTVBMRVggPT0gMiAqIHNpemVvZihkb3VibGUpLCAiKioqIEVSUiAqKioiKTsKCi8vIEwy44Kt44Oj44OD44K344Ol44Grc3Jj44GoZHN044Gu5Lih5pa544GM6KSH57Sg5pWw44GM5LmX44KL5pyA5aSn6KaB57Sg5pWwCiNkZWZpbmUgRVhQTl9DQVBBQ0lUWQkoRVhQTl9MMkNIQUNIRV9TWiAtIEVYUE5fU0laRU9GX0NPTVBMRVggLSBFWFBOX0wyX1NIQVJJTkdfVEhSRUFEUyAtIDEpCgojaWZkZWYgX1dJTjMyCmludCBmb3Blbl9zX3dycChGSUxFKiogY29uc3QgcF9mcCwgY29uc3QgY2hhciogY29uc3QgZnBhdGgsIGNvbnN0IGNoYXIqIGNvbnN0IG1vZGUpCnsKCXJldHVybiAoaW50KWZvcGVuX3MocF9mcCwgZnBhdGgsIG1vZGUpOwp9CmludCBzcHJpbnRmX3Nfd3JwKGNoYXIgYnVmW10sIGNvbnN0IHNpemVfdCBidWZzeiwgY29uc3QgY2hhciogY29uc3QgZm10LCAuLi4pCnsKCXZhX2xpc3QgYXA7CglpbnQgblJldDsKCgl2YV9zdGFydChhcCwgZm10KTsKCW5SZXQgPSB2c3ByaW50Zl9zKGJ1ZiwgYnVmc3osIGZtdCwgYXApOwoJdmFfZW5kKGFwKTsKCglyZXR1cm4gblJldDsKfQojZWxzZQppbnQgZm9wZW5fc193cnAoRklMRSoqIGNvbnN0IHBfZnAsIGNvbnN0IGNoYXIqIGNvbnN0IGZwYXRoLCBjb25zdCBjaGFyKiBjb25zdCBtb2RlKQp7CgkqcF9mcCA9IGZvcGVuKGZwYXRoLCBtb2RlKTsKCXJldHVybiAoKnBfZnAgPT0gTlVMTCk7Cn0KaW50IHNwcmludGZfc193cnAoY2hhciBidWZbXSwgY29uc3Qgc2l6ZV90IGJ1ZnN6LCBjb25zdCBjaGFyKiBjb25zdCBmbXQsIC4uLikKewoJdmFfbGlzdCBhcDsKCWludCBuUmV0OwoKCXZhX3N0YXJ0KGFwLCBmbXQpOwoJblJldCA9IHZzcHJpbnRmKGJ1ZiwgZm10LCBhcCk7Cgl2YV9lbmQoYXApOwoKCXJldHVybiBuUmV0Owp9CiNkZWZpbmUgX2NvdW50b2YoYXJyKQkoc2l6ZW9mKGFycikgLyBzaXplb2YoYXJyWzBdKSkKI2VuZGlmCgovLy8g5a6f6YOo44Go6Jma6YOo44GM5Lqk5Luj44Gr5Lim44G25b2i5byP44Gu6KSH57Sg5pWw44Oq44K544OI44KS6KGo56S644GZ44KL44CCCnZvaWQgc2hvd19yZV9pbV9zZXEoY29uc3Qgc3RkOjp2ZWN0b3I8ZG91YmxlPiYgcywgY29uc3QgaW50IHApCnsKCWNvbnN0IHNpemVfdCBoc3ogPSAoc2l6ZV90KTEgPDwgKHAgLSAxKTsKCglwcmludGYoIlJlOiIpOwoJZm9yIChzaXplX3QgaSA9IDA7IGkgPCBoc3o7IGkrKykgewoJCXByaW50ZigiICUgMTJmIiwgc1syICogaV0pOwoJfQoJcHJpbnRmKCJcbiIpOwoJcHJpbnRmKCJJbToiKTsKCWZvciAoc2l6ZV90IGkgPSAwOyBpIDwgaHN6OyBpKyspIHsKCQlwcmludGYoIiAlIDEyZiIsIHNbMiAqIGkgKyAxXSk7Cgl9CglwcmludGYoIlxuIik7Cn0KCi8vLyDlrp/pg6jjgajomZrpg6jjgYzkuqTku6PjgavkuKbjgbblvaLlvI/jga7opIfntKDmlbDjg6rjgrnjg4jjgpLooajnpLrjgZnjgovjgIIKdm9pZCBzaG93X3JlX2ltX3NlcShjb25zdCBzdGQ6OnZlY3RvcjxJX1RZUEU+JiBzLCBjb25zdCBpbnQgcCkKewoJY2hhciBmbXRbMTI4XTsKCXNwcmludGZfc193cnAoZm10LCBfY291bnRvZihmbXQpLCAiJSUwJWRsdSIsIEZJRyk7CgoJY29uc3Qgc2l6ZV90IGhzeiA9IChzaXplX3QpMSA8PCAocCAtIDEpOwoJcHJpbnRmKCJSZToiKTsKCWZvciAoc2l6ZV90IGkgPSAwOyBpIDwgaHN6OyBpKyspIHsKCQlwcmludGYoZm10LCBzWzIgKiBpXSk7Cgl9CglwcmludGYoIlxuIik7CglwcmludGYoIkltOiIpOwoJZm9yIChzaXplX3QgaSA9IDA7IGkgPCBoc3o7IGkrKykgewoJCXByaW50ZihmbXQsIHNbMiAqIGkgKyAxXSk7Cgl9CglwcmludGYoIlxuIik7Cn0KCm5hbWVzcGFjZSBwcmlyb290CnsKCS8vIOODh+ODvOOCv+OBruahgeaVsOOBruahgeaVsOOCkuihqOOBmeWeiwoJdHlwZWRlZiBpbnQgZXhwbl90OwoKCS8vIOODh+ODvOOCv+OBruahgeaVsOOCkuihqOOBmeWeiwoJdHlwZWRlZiBpbnQ2NF90IHBvd190OwoKI2lmZGVmIFNIT1dfU0lOX1RBQkxFCglzaXplX3QgZ19zaW5fdGJsZW50X2NudCA9IDA7CiNlbmRpZgoKCS8vLyAx44Gu5Y6f5aeLbuS5l+agueOCkuihqOOBmeOAggoJLy8vIG7jga7libDkvZnoqIjnrpfjgpLpq5jpgJ/ljJbjgZnjgovjgZ/jgoHjgIFu44GvMl5w44Gr5Yi26ZmQ44GZ44KL44CCCgljbGFzcyBiYXNpY19udGhfcm9vdAoJewoJCS8qY29uc3QqLyBleHBuX3Qgc3ZfcDsKCQkvKmNvbnN0Ki8gcG93X3QgdDM2MDsKCQkvKmNvbnN0Ki8gcG93X3QgbTM2MDsKCQkvKmNvbnN0Ki8gcG93X3QgdDA5MDsKCQlzdGQ6OnZlY3Rvcjxkb3VibGU+IG1fc2luOwoKCXB1YmxpYzoKCQliYXNpY19udGhfcm9vdCgpIDogc3ZfcCgwKSwgdDM2MCgwKSwgbTM2MCgwKSwgdDA5MCgwKSB7IH0KCQliYXNpY19udGhfcm9vdChjb25zdCBleHBuX3QgcCkKCQkJOiBzdl9wKHApLCB0MzYwKChwb3dfdCkxIDw8IHApLCBtMzYwKHQzNjAgLSAxKSwgdDA5MCh0MzYwIC8gNCksIG1fc2luKChzaXplX3QpKHQzNjAgLyA0ICsgMSkpCgkJewoJCQlpZiAocCA+PSAyKSB7CgkJCQlhc3NlcnQodDM2MCA+PSA0KTsKCQkJCXQwOTAgPSB0MzYwIC8gNDsKCQkJCWNvbnN0IGRvdWJsZSBrID0gMC41ICogTV9QSTsKCQkJCWZvciAocG93X3QgaSA9IDE7IGkgPCB0MDkwOyBpKyspIHsKCQkJCQltX3NpbltpXSA9IHNpbigoayAqIChkb3VibGUpaSkgLyAoZG91YmxlKXQwOTApOwoJCQkJfQojaWZkZWYgU0hPV19TSU5fVEFCTEUKCQkJCWdfc2luX3RibGVudF9jbnQgKz0gdDA5MDsKCQkJCXByaW50ZigiKioqKioqKiAlczogcD0lZCB0YWJsZSBtYWRlLiAoKyV6dSwgJXp1KVxuIiwgX19GVU5DVElPTl9fLCBwLCB0MDkwLCBnX3Npbl90YmxlbnRfY250KTsKI2VuZGlmCgkJCQltX3NpblswXSA9IDAuMDsKCQkJCW1fc2luW3QwOTBdID0gMS4wOwoJCQl9CgkJfQoKCQlleHBuX3QgcCgpIGNvbnN0IHsgcmV0dXJuIHN2X3A7IH0KCgkJcG93X3QgbigpIGNvbnN0IHsgcmV0dXJuIHQzNjA7IH0KCgkJLy8vIDHjga7ljp/lp4tu5LmX5qC544Gua+S5l+OCkuWPluW+l+OBmeOCi+OAggoJCXZvaWQgcG93KGNvbnN0IHBvd190IGtfLCBkb3VibGUmIHJlLCBkb3VibGUmIGltKSBjb25zdCB7CgkJCWFzc2VydChrXyA+PSAwKTsKCQkJcG93X3QgayA9IGtfOwoJCQlrICY9IG0zNjA7CQkvLyBu44Gu5Ymw5L2ZCgkJCWlmIChzdl9wIDwgMikgewoJCQkJYXNzZXJ0KGsgPT0gMCB8fCBrID09IDEpOwoJCQkJaW0gPSAwLjA7CgkJCQlyZSA9IChrID09IDApID8gMS4wIDogLTEuMDsKCQkJCXJldHVybjsKCQkJfQoJCQlhc3NlcnQoMCA8PSBrICYmIGsgPCA0ICogdDA5MCk7CgkJCWlmIChrIDw9IHQwOTApIHsKCQkJCXJlID0gbV9zaW5bdDA5MCAtIGtdOwoJCQkJaW0gPSBtX3NpbltrXTsKCQkJfQoJCQllbHNlIGlmIChrIDw9IDIgKiB0MDkwKSB7CgkJCQlyZSA9IC1tX3NpbltrIC0gdDA5MF07CQkJLy8gPSB0MDkwIC0gKDIgKiB0MDkwIC0gaykKCQkJCWltID0gbV9zaW5bMiAqIHQwOTAgLSBrXTsKCQkJfQoJCQllbHNlIGlmIChrIDw9IDMgKiB0MDkwKSB7CgkJCQlyZSA9IC1tX3NpblszICogdDA5MCAtIGtdOwkJLy8gPSB0MDkwIC0gKGsgLSAyICogdDA5MCkKCQkJCWltID0gLW1fc2luW2sgLSAyICogdDA5MF07CgkJCX0KCQkJZWxzZSB7CgkJCQlyZSA9IG1fc2luW2sgLSAzICogdDA5MF07CQkvLyA9IHQwOTAgLSAoNCAqIHQwOTAgLSBrKQoJCQkJaW0gPSAtbV9zaW5bNCAqIHQwOTAgLSBrXTsKCQkJfQoJCX0KCgl9OwoKCS8vLyAx44Gu5Y6f5aeLbuS5l+agueOCkuihqOOBmeOAggoJY2xhc3MgbnRoX3Jvb3QKCXsKCQlleHBuX3QgbWF4X3A7CgoJCS8vIDHjga7ljp/lp4syXnDkuZfmoLnjga5y5LmX44KS5Y+O44KB44Gf44OG44O844OW44Or44Gu44OZ44Kv44K/CgkJLy8gYmFzaWNfdGFibGVzW3Bd44GMMeOBruWOn+WnizJecOS5l+agueOBruODhuODvOODluODq+OCkuihqOOBmeOAggoJCXN0ZDo6dmVjdG9yPGJhc2ljX250aF9yb290PiBiYXNpY190YWJsZXM7CgoJCS8vIDHjga7ljp/lp4syXihwK20p5LmX5qC544Gu44G/44KS5Y+O44KB44Gf44OZ44Kv44K/CgkJLy8gaGlnaF9vcmRlcl9yb290X3RhYmxlc1ttXeOBjDHjga7ljp/lp4syXihwK20p5LmX5qC544Gu5YCk44CCKOOBk+OBoeOCieOBr+ODmeOCr+OCv+imgee0oOOBjOODhuODvOODluODq+OBp+OBr+OBquOBj+WApOOCkuihqOOBmeOAgikKCQlzdGQ6OnZlY3RvcjxzdGQ6OnBhaXI8ZG91YmxlLCBkb3VibGU+ID4gaGlnaF9vcmRlcl9yb290X3ZhbHVlczsKCgkJLyoKCQkJKE5PVEUpCgkJCTHjga7ljp/lp4tu5LmX5qC544KSd19u44Go5pu444GP44GT44Go44Gr44GZ44KL44Go44CBeyBiX24gfeOCkjDjgYsx44GL44KJ44Gq44KL5pWw5YiX44CBcuOCkumBqeW9k+OBquaVtOaVsOOBqOOBl+OBpgoJCQnjgIDjgIBrID0gYl8wICsgMiAqIGJfMSArICgyXjIpICogYl8yICsgLi4uICogKDJeKG0tMSkpICogYl8obS0xKSArIHsgKDJebSkgKiByIH0KCQkJ44Gn44GC44KL44Go44GN44CBCgkJCQkod18oMl4ocCttKSkpXmsgPSB3XygyXihwK20pKV5iXzAgKiB3XygyXihwKyhtLTEpKSleYl8xICogd18oMl4ocCsobS0yKSleYl8yICogLi4uICogd18oMl4ocCsxKSleYl8obS0xKSAqIHsgd19wXihy44GuMl5w44Gr5a++44GZ44KL5Ymw5L2ZKSB9CgkJCeOBqOabuOOBkeOCi+OBruOBp+OAgQoJCQkJd19wXnIgKHI9MC4uKDJecC0xKSkg44Gu5YCkCgkJCQl3XzJeKHArcSkgIChxPTEuLm0pIOOBruWApAoJCQnjgYzjgYLjgozjgbDjgIEod14ocCttKSleayDjgpLoqIjnrpfjgafjgY3jgovjgIIKCQkJ5YmN6ICF44Gv5Lu75oSP44Gu5oyH5pWwcuOBq+OBpOOBhOOBpuioiOeul+OBp+OBjeOBreOBsOOBquOCieOBquOBhOOBn+OCgeOAgeODhuODvOODluODq+OBp+Wun+ePvuOBmeOCi+WgtOWQiOOBr08oMl5wKeOCquODvOODgOODvOOBruODoeODouODquOCkuimgeOBmeOCi+OBjOOAgQoJCQnlvozogIXjga9t5YCL44Gu5YCk44Gg44GR6KiY5oa244GX44Gm44GK44GR44Gw6Imv44GE44Gf44KB44CBTyhtKeOBruOCquODvOODgOODvOOBp+a4iOOCgOOAguOBneOBruOBi+OCj+OCimvjgYzkuI7jgYjjgonjgozjgovpg73luqblgKTjga7mjpvjgZHnrpfjgYznmbrnlJ/jgZnjgovjgIIKCQkqLwoKCXB1YmxpYzoKCQludGhfcm9vdCgpIDogbWF4X3AoMCkgeyB9CgoJCS8vLyAx44Gu5Y6f5aeLMl5w5LmX5qC544Gu44OG44O844OW44Or44KS55So5oSP44GZ44KL44CCCgkJdm9pZCBhbGxvY190YWJsZShjb25zdCBleHBuX3QgcCkgewoJCQlpZiAocCA+IG1heF9wKSB7CgkJCQkvLyAo44OG44O844OW44Or55Sf5oiQ5riI44GucOOCiOOCiuWkp+OBjeOBhHApCgkJCQkvLyDjgb7jgZrjg4bjg7zjg5bjg6vnlJ/miJDjgpLmpJzoqI7jgZnjgovjgIIKCQkJCWlmIChwIDw9IEJBU0lDX1NJTlRCTF9QX01BWCkgewoJCQkJCS8vIChw44GM5Yi26ZmQ5YCk5Lul5LiLKQoJCQkJCS8vIFttYXhfcCsxLi5wXeOBruODhuODvOODluODq+OCkuaWsOimj+eUn+aIkAoJCQkJCWJhc2ljX3RhYmxlcy5yZXNpemUoKHNpemVfdCkocCArIDEpKTsKCQkJCQlmb3IgKGV4cG5fdCBpID0gbWF4X3AgKyAxOyBpIDw9IHA7IGkrKykgewoJCQkJCQliYXNpY190YWJsZXNbaV0gPSBiYXNpY19udGhfcm9vdChpKTsKCQkJCQl9CgkJCQkJbWF4X3AgPSBwOwoJCQkJfQoJCQl9CgoJCQlpZiAocCA+IG1heF9wKSB7CgkJCQkvLyAo5Lu75oSP5oyH5pWw44Gr5a++44GZ44KL44OG44O844OW44Or5YyW44GM5LiN6IO944Gq5aSn44GN44GV44GucCkKCQkJCS8vIOaMh+aVsGs9MeOBruWApOOBruOBv+iomOaGtuOBmeOCi+OAggoJCQkJY29uc3QgZXhwbl90IG0gPSBwIC0gbWF4X3A7CgkJCQlpZiAoKHNpemVfdCltID49IGhpZ2hfb3JkZXJfcm9vdF92YWx1ZXMuc2l6ZSgpKSB7CgkJCQkJaGlnaF9vcmRlcl9yb290X3ZhbHVlcy5yZXNpemUoKHNpemVfdCkobSArIDEpKTsKCQkJCQlzdGQ6OnBhaXI8ZG91YmxlLCBkb3VibGU+JiBlbnQgPSBoaWdoX29yZGVyX3Jvb3RfdmFsdWVzW21dOwkJLy8gQWxpYXMKCQkJCQljb25zdCBwb3dfdCBiaWdfbiA9IChwb3dfdCkxIDw8IHA7CgkJCQkJY29uc3QgZG91YmxlIGFyZyA9ICgyICogTV9QSSkgLyBiaWdfbjsKCQkJCQllbnQuZmlyc3QgPSBjb3MoYXJnKTsJCS8vIOWun+mDqAoJCQkJCWVudC5zZWNvbmQgPSBzaW4oYXJnKTsJCS8vIOiZmumDqAoJCQkJfQoJCQl9CgkJfQoKCQkvLy8gMeOBruWOn+WnizJecOS5l+agueOBrmvkuZfjgpLlj5blvpfjgZnjgovjgIIKCQl2b2lkIHBvdyhjb25zdCBleHBuX3QgcCwgY29uc3QgcG93X3QgaywgZG91YmxlJiByZSwgZG91YmxlJiBpbSkgY29uc3QgewoJCQlpZiAocCA8PSBtYXhfcCkgewoJCQkJLy8gKHdfKDJecCkpXmvnrpflh7oKCQkJCWJhc2ljX3RhYmxlc1twXS5wb3coaywgcmUsIGltKTsKCQkJfQoJCQllbHNlIHsKCQkJCWNvbnN0IGV4cG5fdCBtID0gcCAtIG1heF9wOwoJCQkJY29uc3QgcG93X3QgciA9IGsgPj4gbTsKCQkJCWNvbnN0IHBvd190IGIgPSBrICYgKCgocG93X3QpMSA8PCBtKSAtIDEpOwoKCQkJCS8vICh3XygyXm1heF9wKSlecueul+WHugoJCQkJYmFzaWNfdGFibGVzW21heF9wXS5wb3cociwgcmUsIGltKTsKCgkJCQkvLyB3XygyXihtYXhfcCArIGkpKeOCkuaOm+OBkeWQiOOCj+OBm+OCiwoJCQkJcG93X3QgbWFzayA9IChwb3dfdCkxIDw8IChtIC0gMSk7CgkJCQlmb3IgKGV4cG5fdCBpID0gMTsgaSA8PSBtOyBpKyspIHsKCQkJCQlhc3NlcnQobWFzayA+IDApOwoJCQkJCWlmICgoYiAmIG1hc2spICE9IDApIHsKCQkJCQkJY29uc3Qgc3RkOjpwYWlyPGRvdWJsZSwgZG91YmxlPiYgZW50ID0gaGlnaF9vcmRlcl9yb290X3ZhbHVlc1tpXTsJCS8vIEFsaWFzCgkJCQkJCWNvbnN0IGRvdWJsZSB0bXBfcmUgPSByZSAqIGVudC5maXJzdCAtIGltICogZW50LnNlY29uZDsKCQkJCQkJY29uc3QgZG91YmxlIHRtcF9pbSA9IHJlICogZW50LnNlY29uZCArIGltICogZW50LmZpcnN0OwoJCQkJCQlyZSA9IHRtcF9yZTsKCQkJCQkJaW0gPSB0bXBfaW07CgkJCQkJfQoJCQkJCW1hc2sgPj49IDE7CgkJCQl9CgkJCQlhc3NlcnQobWFzayA9PSAwKTsKCQkJfQoJCX0KCgl9OwoKfQkvLyBuYW1lc3BhY2UgcHJpcm9vdAoKbmFtZXNwYWNlIGZmdG4KewoJdXNpbmcgbmFtZXNwYWNlIHByaXJvb3Q7CgoJLy8vIOODk+ODg+ODiOaVsGJpdHfjga5CVFLmvJTnrpcKCXBvd190IGJ0cihjb25zdCBwb3dfdCB4LCBjb25zdCBleHBuX3QgYml0dykgewoJCXBvd190IHkgPSAwOwoJCWZvciAoZXhwbl90IGkgPSAwOyBpIDw9IChiaXR3IC0gMSkgLyAyOyBpKyspIHsKCQkJY29uc3QgcG93X3QgYiA9ICgocG93X3QpMSA8PCBpKSAmIHg7CgkJCXkgfD0gKGIgPDwgKChiaXR3IC0gMSkgLSAyICogaSkpOwoJCX0KCQlmb3IgKGV4cG5fdCBpID0gKGJpdHcgLSAxKSAvIDIgKyAxOyBpIDwgYml0dzsgaSsrKSB7CgkJCWNvbnN0IHBvd190IGIgPSAoKHBvd190KTEgPDwgaSkgJiB4OwoJCQl5IHw9IChiID4+ICgyICogaSAtIChiaXR3IC0gMSkpKTsKCQl9CgkJcmV0dXJuIHk7Cgl9CgoJLy8vIOODleODvOODquOCqOWkieaPmwoJLy8vIERGVOOBruWOn+eQhuW8jwoJLy8vICAgWChrKSA9IM6jW2o9MC4udDM2MC0xXXsgeChqKSAqIHdeKGoqaykgfSAgKGs9MC4udDM2MC0xKQoJLy8vIOOCiOOCigoJLy8vICAgWChrKSA9IM6jW2o9MC4udDE4MC0xXXsgeCgyKmopICogd14oMipqKmspIH0gKyDOo1tqPTAuLnQxODAtMV17IHgoMipqKzEpICogd14oKDIqaisxKSprKSB9CgkvLy8gICAgICAgID0gzqNbaj0wLi50MTgwLTFdeyB4KDIqaikgKiB3XigyKmoqaykgfSArIHdeayAqIM6jW2o9MC4udDE4MC0xXXsgeCgyKmorMSkgKiB3XigyKmoqaykgfQoJLy8vIOOBleOCieOBq+OAgWvjgpJrK3QxODDjgavnva7jgY3mj5vjgYjjgovjgajku6XkuIvjgYzmiJDnq4vjgZnjgovjgIIKCS8vLyAgIFgoayt0MTgwKSA9IM6jW2o9MC4udDE4MC0xXXsgeCgyKmopICogd14oMipqKihrICsgdDE4MCkgfSArIHdeKGsrdDE4MCkgKiDOo1tqPTAuLnQxODAtMV17IHgoMipqKzEpICogd14oMipqKihrK3QxODApIH0KCS8vLyAgICAgICAgICAgICA9IM6jW2o9MC4udDE4MC0xXXsgeCgyKmopICogd14oMipqKmspICAgICAgICAgfSAtIHdeayAgICAgICAgKiDOo1tqPTAuLnQxODAtMV17IHgoMipqKzEpICogd14oMipqKmspIH0KCS8vLyDjgojjgaPjgabjgIEKCS8vLyAgIFhfZXZlbihrKSA9IM6jW2o9MC4udDE4MC0xXXsgeCgyKmogICkgKiB3XigyKmoqaykgfSAoaz0wLi50MTgwLTEpCgkvLy8gICBYX29kZChrKSAgPSDOo1tqPTAuLnQxODAtMV17IHgoMipqKzEpICogd14oMipqKmspIH0gKGs9MC4udDE4MC0xKQoJLy8vIOOBqOOBl+OBpuOAgVgoaykgKGs9MC4udDM2MCnjga/ku6XkuIvjga7jg5Djgr/jg5Xjg6njgqTmvJTnrpfjgafooajjgZvjgovjgIIKCS8vLyDjgIBYKGsgICAgICkgPSBYX2V2ZW4oaykgKyB3XmsgKiBYX29kZChrKSAoaz0wLi50MTgwLTEpCgkvLy8gICBYKGsrdDE4MCkgPSBYX2V2ZW4oaykgLSB3XmsgKiBYX29kZChrKSAoaz0wLi50MTgwLTEpCgkvLy8g44GT44KM44KS44CB5aSn5YWD44Gu5pmC6ZaT6aCY5Z+f44OH44O844K/eChqKeOBruWun+mDqOOBjGJ1ZlsyKmpd44CB6Jma6YOo44GMYnVmWzIqaiArIDFd44Gr5qC857SN44GV44KM44Gm44GE44KL5YmN5o+Q44Gn6KGM44GG44CCCgl2b2lkIGZvdXJpKAoJCXN0ZDo6dmVjdG9yPGRvdWJsZT46Oml0ZXJhdG9yIGJ1ZiwKCQljb25zdCBleHBuX3QgcCwKCQludGhfcm9vdCYgdykKCXsKCQkvLyDlho3luLDntYLnq6/liKTlrpoKCQlpZiAocCA9PSAwKSB7CgkJCS8vICjopoHntKDmlbAyXjDjga7jg5Xjg7zjg6rjgqjlpInmj5spCgkJCS8vIOWNmOS4gOimgee0oHgoainjga7jg5Xjg7zjg6rjgqjlpInmj5vjga94KGop44Gq44Gu44Gn5L2V44KC44GX44Gq44GE44CCCgkJCXJldHVybjsKCQl9CgoJCWNvbnN0IHBvd190IHQzNjAgPSAocG93X3QpMSA8PCBwOwoJCWNvbnN0IHBvd190IHQxODAgPSAocG93X3QpMSA8PCAocCAtIDEpOwoKCQl3LmFsbG9jX3RhYmxlKHApOwoKCQkvLyBYX2V2ZW4oaynlj5blvpcKCQkvLyBbMC4udDE4MC0xXeOBq+WvvuOBl+OAgXdeMmvjgpLlm57ou6Llm6DlrZDjgajjgZnjgovjg5Xjg7zjg6rjgqjlpInmj5vjgpJpbi1wbGFjZeOBp+Wun+ihjOOBmeOCi+OAggoJCWZvdXJpKGJ1ZiwgcCAtIDEsIHcpOwoKCQkvLyBYX29kZChrKeWPluW+lwoJCS8vIFt0MTgwLi50MzYwLTFd44Gr5a++44GX44CBd14ya+OCkuWbnui7ouWboOWtkOOBqOOBmeOCi+ODleODvOODquOCqOWkieaPm+OCkmluLXBsYWNl44Gn5a6f6KGM44GZ44KL44CCCgkJLy8gdDE4MOOBqzLjgpLmjpvjgZHjgabjgYTjgovjga7jga/jgIHlrp/pg6jjgajomZrpg6jjga4y6KaB57Sg44K744OD44OI44GndDAwMeOBp+OBguOCi+OBk+OBqOOBq+OCiOOCi+OAggoJCWZvdXJpKGJ1ZiArIDIgKiB0MTgwLCBwIC0gMSwgdyk7CgoJCS8vIOODkOOCv+ODleODqeOCpOa8lOeulwoJCS8vIFgoayAgICAgKSA9IFhfZXZlbihrKSArIHdeayAqIFhfb2RkKGspCgkJLy8gWChrK3QxODApID0gWF9ldmVuKGspIC0gd15rICogWF9vZGQoaykKCQlmb3IgKHBvd190IGsgPSAwOyBrIDwgdDE4MDsgaysrKSB7CgkJCWNvbnN0IHBvd190IG9mc19ldmVuID0gayA8PCAxOwoJCQljb25zdCBwb3dfdCBvZnNfb2RkID0gKGsgKyB0MTgwKSA8PCAxOwoKCQkJLy8gWF9ldmVuKGspCgkJCWNvbnN0IGRvdWJsZSBYX2V2ZW5fa19yZSA9IGJ1ZltvZnNfZXZlbl07CgkJCWNvbnN0IGRvdWJsZSBYX2V2ZW5fa19pbSA9IGJ1ZltvZnNfZXZlbiArIDFdOwoKCQkJLy8gWF9vZGQoaykKCQkJZG91YmxlIFhfb2RkX2tfcmUgPSBidWZbb2ZzX29kZF07CgkJCWRvdWJsZSBYX29kZF9rX2ltID0gYnVmW29mc19vZGQgKyAxXTsKCgkJCS8vIFhfb2RkKGspICogd15rIOeul+WHuuOAgeOBk+OBk+OBp3fjga8x44Gu5Y6f5aeLdDM2MOS5l+aguQoJCQlkb3VibGUgd2tfcmUsIHdrX2ltOwoJCQl3LnBvdyhwLCBrLCB3a19yZSwgd2tfaW0pOwoJCQljb25zdCBkb3VibGUgcmUgPSBYX29kZF9rX3JlICogd2tfcmUgLSBYX29kZF9rX2ltICogd2tfaW07CgkJCWNvbnN0IGRvdWJsZSBpbSA9IFhfb2RkX2tfcmUgKiB3a19pbSArIFhfb2RkX2tfaW0gKiB3a19yZTsKCgkJCS8vIFgoayAgICAgKSA9IFhfZXZlbihrKSArIHdeayAqIFhfb2RkKGspID0gWF9ldmVuKGspICsgKHJlICsgaSAqIGltKQoJCQlidWZbb2ZzX2V2ZW5dID0gWF9ldmVuX2tfcmUgKyByZTsKCQkJYnVmW29mc19ldmVuICsgMV0gPSBYX2V2ZW5fa19pbSArIGltOwoKCQkJLy8gWChrK3QxODApID0gWF9ldmVuKGspIC0gd15rICogWF9vZGQoaykgPSBYX2V2ZW4oaykgLSAocmUgKyBpICogaW0pCgkJCWJ1ZltvZnNfb2RkXSA9IFhfZXZlbl9rX3JlIC0gcmU7CgkJCWJ1ZltvZnNfb2RkICsgMV0gPSBYX2V2ZW5fa19pbSAtIGltOwoJCX0KCX0KCgkvLy8gQml0IHJldmVyc2Ugb3JkZXLjgatpbi1wbGFjZeOBp+S4puOBueabv+OBiOOCi+OAggoJdm9pZCBzb3J0X2J5X2J0cigKCQlzdGQ6OnZlY3Rvcjxkb3VibGU+OjppdGVyYXRvciBidWYsCgkJY29uc3QgZXhwbl90IHApCgl7CgkJY29uc3QgcG93X3QgdDM2MCA9IChwb3dfdCkxIDw8IHA7CgoJCWZvciAocG93X3QgaSA9IDA7IGkgPCB0MzYwOyBpKyspIHsKCQkJY29uc3QgcG93X3QgYnRyX2kgPSBidHIoaSwgcCk7CgoJCQkvLyAoYnRyX2ksIGkp44GoKGksIGJ0cl9pKeOBruS4oeaWueOBq+OBpOOBhOOBpnN3YXDjgZnjgovjgajlhYPjgavmiLvjgaPjgabjgZfjgb7jgYbjga7jgafjgIEKCQkJLy8g54mH5pa544Gu44G/c3dhcOWvvuixoeOBqOOBmeOCi+OAggoJCQlpZiAoYnRyX2kgPCBpKSB7CgkJCQlzdGQ6OnN3YXAoYnVmWzIgKiBidHJfaV0sIGJ1ZlsyICogaV0pOwkJCQkvLyDlrp/pg6gKCQkJCXN0ZDo6c3dhcChidWZbMiAqIGJ0cl9pICsgMV0sIGJ1ZlsyICogaSArIDFdKTsJCS8vIOiZmumDqAoJCQl9CgkJfQoJfQoKCS8vLyDpgIbjg5Xjg7zjg6rjgqjlpInmj5sKCS8vLyDjg5Xjg7zjg6rjgqjlpInmj5vjgajjga/pgIbjga7ku6XkuIvjga7jg5Djgr/jg5Xjg6njgqTmvJTnrpfjgpLooYzjgYbjgIIKCS8vLyDjgIB4KGsgICAgICkgPSAoeF9ldmVuKGspICsgd14oLWspICogeF9vZGQoaykpIC8gdDM2MCAoaz0wLi50MTgwLTEpCgkvLy8gICB4KGsrdDE4MCkgPSAoeF9ldmVuKGspIC0gd14oLWspICogeF9vZGQoaykpIC8gdDM2MCAoaz0wLi50MTgwLTEpCgkvLy8g44GT44KM44KS44CB5aSn5YWD44Gu5ZGo5rOi5pWw6aCY5Z+f44OH44O844K/WChrKeOBruWun+mDqOOBjGJ1ZlsyKmtd44CB6Jma6YOo44GMYnVmWzIqaysxXeOBq+agvOe0jeOBleOCjOOBpuOBhOOCi+WJjeaPkOOBp+ihjOOBhuOAggoJdm9pZCBmb3VyaWludigKCQlzdGQ6OnZlY3Rvcjxkb3VibGU+OjppdGVyYXRvciBidWYsCgkJY29uc3QgZXhwbl90IHAsCgkJbnRoX3Jvb3QmIHcpCgl7CgkJLy8g5YaN5biw57WC56uv5Yik5a6aCgkJaWYgKHAgPT0gMCkgewoJCQkvLyAo6KaB57Sg5pWwMl4w44Gu44OV44O844Oq44Ko5aSJ5o+bKQoJCQkvLyDljZjkuIDopoHntKB4KGop44Gu44OV44O844Oq44Ko5aSJ5o+b44GveChqKeOBquOBruOBp+S9leOCguOBl+OBquOBhOOAggoJCQlyZXR1cm47CgkJfQoKCQljb25zdCBwb3dfdCB0MzYwID0gKHBvd190KTEgPDwgcDsKCQljb25zdCBwb3dfdCB0MTgwID0gKHBvd190KTEgPDwgKHAgLSAxKTsKCgkJdy5hbGxvY190YWJsZShwKTsKCgkJLy8geF9ldmVuKGsp5Y+W5b6XCgkJLy8gWzAuLnQxODAtMV3jgavlr77jgZfjgIF3XjJr44KS5Zue6Lui5Zug5a2Q44Go44GZ44KL44OV44O844Oq44Ko5aSJ5o+b44KSaW4tcGxhY2Xjgaflrp/ooYzjgZnjgovjgIIKCQlmb3VyaWludihidWYsIHAgLSAxLCB3KTsKCgkJLy8geF9vZGQoaynlj5blvpcKCQkvLyBbdDE4MC4udDM2MC0xXeOBq+WvvuOBl+OAgXdeMmvjgpLlm57ou6Llm6DlrZDjgajjgZnjgovjg5Xjg7zjg6rjgqjlpInmj5vjgpJpbi1wbGFjZeOBp+Wun+ihjOOBmeOCi+OAggoJCS8vIHQxODDjgasy44KS5o6b44GR44Gm44GE44KL44Gu44Gv44CB5a6f6YOo44Go6Jma6YOo44GuMuimgee0oOOCu+ODg+ODiOOBp3QwMDHjgafjgYLjgovjgZPjgajjgavjgojjgovjgIIKCQlmb3VyaWludihidWYgKyAyICogdDE4MCwgcCAtIDEsIHcpOwoKCQkvLyDjg5Djgr/jg5Xjg6njgqTmvJTnrpcKCQkvLyB4KGsgICAgICkgPSB4X2V2ZW4oaykgKyB3XmsgKiB4X29kZChrKQoJCS8vIHgoayt0MTgwKSA9IHhfZXZlbihrKSAtIHdeayAqIHhfb2RkKGspCgkJZm9yIChwb3dfdCBrID0gMDsgayA8IHQxODA7IGsrKykgewoJCQljb25zdCBwb3dfdCBvZnNfZXZlbiA9IGsgPDwgMTsKCQkJY29uc3QgcG93X3Qgb2ZzX29kZCA9IChrICsgdDE4MCkgPDwgMTsKCgkJCS8vIHhfZXZlbihrKQoJCQljb25zdCBkb3VibGUgeF9ldmVuX2tfcmUgPSBidWZbb2ZzX2V2ZW5dOwoJCQljb25zdCBkb3VibGUgeF9ldmVuX2tfaW0gPSBidWZbb2ZzX2V2ZW4gKyAxXTsKCgkJCS8vIHhfb2RkKGspCgkJCWRvdWJsZSB4X29kZF9rX3JlID0gYnVmW29mc19vZGRdOwoJCQlkb3VibGUgeF9vZGRfa19pbSA9IGJ1ZltvZnNfb2RkICsgMV07CgoJCQkvLyB4X29kZChrKSAqIHdeKC1rKSDnrpflh7rjgIHjgZPjgZPjgad344GvMeOBruWOn+Wni3QzNjDkuZfmoLkKCQkJZG91YmxlIHdrX3JlLCB3a19pbTsKCQkJdy5wb3cocCwgaywgd2tfcmUsIHdrX2ltKTsKCQkJY29uc3QgZG91YmxlIHJlID0geF9vZGRfa19yZSAqIHdrX3JlICsgeF9vZGRfa19pbSAqIHdrX2ltOwoJCQljb25zdCBkb3VibGUgaW0gPSB4X29kZF9rX2ltICogd2tfcmUgLSB4X29kZF9rX3JlICogd2tfaW07CgoJCQkvLyBYKGsgICAgICkgPSB4X2V2ZW4oaykgKyB3XmsgKiB4X29kZChrKSA9IHhfZXZlbihrKSArIChyZSArIGkgKiBpbSkKCQkJYnVmW29mc19ldmVuXSA9ICh4X2V2ZW5fa19yZSArIHJlKSAvIDIuMDsKCQkJYnVmW29mc19ldmVuICsgMV0gPSAoeF9ldmVuX2tfaW0gKyBpbSkgLyAyLjA7CgoJCQkvLyBYKGsrdDE4MCkgPSB4X2V2ZW4oaykgLSB3XmsgKiB4X29kZChrKSA9IHhfZXZlbihrKSAtIChyZSArIGkgKiBpbSkKCQkJYnVmW29mc19vZGRdID0gKHhfZXZlbl9rX3JlIC0gcmUpIC8gMi4wOwoJCQlidWZbb2ZzX29kZCArIDFdID0gKHhfZXZlbl9rX2ltIC0gaW0pIC8gMi4wOwoJCX0KCX0KCn0JLy8gbmFtZXNwYWNlIGZmdG4KCi8vIOODluODreODg+OCr1NpeC1TdGVwIEZGVOOCouODq+OCtOODquOCuuODoAovLyBodHRwczovL3cuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmMuanAvcHVibGljL1ZPTDkvc3BlY2lhbC83LnBkZgovLyDjga5DKyvlrp/oo4UKLy8g5a6f6KOF44Gu6YO95ZCI44Gr44KI44KK44CB6KGM5pWwbjHjgIHliJfmlbBuMuOAgeODluODreODg+OCr+OBruihjOaVsG5i44GvMuOBruWGquOBq+WItumZkOOBmeOCi+OAggovLyDjgb7jgZ/jgIFQQ+OCueOCv+ODs+ODieOCouODreODs+Wun+ihjOeUqOOBq+ihjOWIl+i7oue9ruWHpueQhuOCkuewoee0oOWMluOBl+OBpuOBhOOCi+OAggpuYW1lc3BhY2UgZmZ0YjYKewoJdXNpbmcgbmFtZXNwYWNlIHByaXJvb3Q7CgoJLy8vIOacgOmBqeOBquihjOaVsCgy44Gu5YaqKeOBruaMh+aVsOOCkui/lOOBmeOAggoJZXhwbl90IGdldF9iZXN0X2V4cG5fbjEoY29uc3QgZXhwbl90IHApCgl7CgkJY29uc3QgZXhwbl90IGV4cF9leHBuX24xID0gKHAgKyAxKSAvIDI7CgkJcmV0dXJuIHN0ZDo6bWluKGV4cF9leHBuX24xLCBFWFBOX0NBUEFDSVRZKTsKCX0KCgkvLy8g5pyA6YGp44Gq44OW44Ot44OD44Kv44K144Kk44K6KDLjga7lhqop44Gu5oyH5pWw44KS6L+U44GZ44CCCglleHBuX3QgZ2V0X2Jlc3RfZXhwbl9uYihjb25zdCBleHBuX3QgZXhwbl9uKQoJewoJCXJldHVybiBzdGQ6Om1pbihleHBuX24sIChFWFBOX0NBUEFDSVRZID4gZXhwbl9uKSA/IEVYUE5fQ0FQQUNJVFkgLSBleHBuX24gOiAwKTsKCX0KCgkvLy8g6Lui572u5Yem55CGCgkvLy8g6Lui572u5YWD6YWN5YiXc3JjW13jga8gKDJeZXhwbl9uMSnooYwoMl4ocC1leHBuX24xKSnliJfjga4y5qyh5YWD6YWN5YiXCgkvLy8g6Lui572u5YWI6YWN5YiXZHN0W13jga8gKDJeKHAtZXhwbl9uMSkp6KGMKDJeZXhwbl9uMSnliJfjga4y5qyh5YWD6YWN5YiXCgkvLy8g44Go44Gd44KM44Ge44KM6Kej6YeI44GZ44KL44CCCgl2b2lkIHRyYW5zcG9zZSgKCQlzdGQ6OnZlY3Rvcjxkb3VibGU+Ojpjb25zdF9pdGVyYXRvciBzcmMsCgkJc3RkOjp2ZWN0b3I8ZG91YmxlPjo6aXRlcmF0b3IgZHN0LAoJCWNvbnN0IGV4cG5fdCBwLAoJCWNvbnN0IGV4cG5fdCBleHBuX24xKQoJewoJCWNvbnN0IGV4cG5fdCBleHBuX24yID0gcCAtIGV4cG5fbjE7CgoJCWNvbnN0IHBvd190IHQzNjAgPSAocG93X3QpMSA8PCBwOwoJCWNvbnN0IHBvd190IG4xID0gKHBvd190KTEgPDwgZXhwbl9uMTsKCQljb25zdCBwb3dfdCBuMiA9IChwb3dfdCkxIDw8IGV4cG5fbjI7CgoJCS8vIOOCueODiOODrOODvOODiOOBqui7oue9ruOCouODq+OCtOODquOCuuODoAoJCS8vIOato+aWueihjOWIl+OBrui7oue9ruOBuOOBruWIhuino+OBr1BD44K544K/44Oz44OJ44Ki44Ot44Oz5a6f6KGM44Gr5ZCR44GL44Gq44GE44Gf44KB6KGM44KP44Gq44GE44CCCiNwcmFnbWEgb21wIHBhcmFsbGVsIGZvcgoJCWZvciAocG93X3QgaSA9IDA7IGkgPCBuMTsgaSsrKSB7CgkJCWZvciAocG93X3QgaiA9IDA7IGogPCBuMjsgaisrKSB7CgkJCQljb25zdCBwb3dfdCBzcmNfaWR4ID0gbjIgKiBpICsgajsKCQkJCWNvbnN0IHBvd190IGRzdF9pZHggPSBuMSAqIGogKyBpOwoKCQkJCWRzdFsyICogZHN0X2lkeF0gPSBzcmNbMiAqIHNyY19pZHhdOwkJCQkvLyDlrp/pg6gKCQkJCWRzdFsyICogZHN0X2lkeCArIDFdID0gc3JjWzIgKiBzcmNfaWR4ICsgMV07CQkvLyDomZrpg6gKCQkJfQoJCX0KCX0KCgkvLyDliY3mlrnlrqPoqIAKCXZvaWQgZm91cmlfd3JwKAoJCXN0ZDo6dmVjdG9yPGRvdWJsZT46Oml0ZXJhdG9yIGJ1ZiwKCQljb25zdCBleHBuX3QgcCwKCQludGhfcm9vdCYgdyk7Cgl2b2lkIGZvdXJpaW52X3dycCgKCQlzdGQ6OnZlY3Rvcjxkb3VibGU+OjppdGVyYXRvciBidWYsCgkJY29uc3QgZXhwbl90IHAsCgkJbnRoX3Jvb3QmIHcpOwoKCS8vLyDjg5Xjg7zjg6rjgqjlpInmj5sKCXZvaWQgZm91cmliNigKCQlzdGQ6OnZlY3Rvcjxkb3VibGU+OjppdGVyYXRvciBidWYsCgkJY29uc3QgZXhwbl90IHAsCgkJbnRoX3Jvb3QmIHcsCgkJY29uc3QgZXhwbl90IGV4cG5fbjEpCgl7CgkJLy8g6KGM5pWw44GM5YWo5L2T44Gu44K144Kk44K65Lul5LiL44Gn44GC44KL44GT44GoCgkJaWYgKCEoMCA8PSBleHBuX24xICYmIGV4cG5fbjEgPD0gcCkpIHsKCQkJLy8g44GT44GT44Gr5p2l44Gf44KJ5ZG844Gz5Ye644GX5YWD44Gu44OQ44KwCgkJCWFib3J0KCk7CgkJfQoKCQkvLyDliJfmlbAoMuOBruWGqinjga7mjIfmlbAKCQljb25zdCBleHBuX3QgZXhwbl9uMiA9IHAgLSBleHBuX24xOwoKCQkvLyDjg5bjg63jg4Pjgq/jgrXjgqTjgroKCQljb25zdCBleHBuX3QgZXhwbl9uYiA9IGdldF9iZXN0X2V4cG5fbmIoZXhwbl9uMik7CgoJCS8vIGJ1ZlswLi50MzYwLTFd44KS6KSH57Sg5pWw44KS6KaB57Sg44Go44GZ44KLMuasoeWFg+mFjeWIl+OBqOOBv+OBquOBmeOAggoJCS8vIOWFpeWKm+OBq+mWouOBl+OBpuOBryBqPW4yKmoxICsgajIgKDDiiaZqMu+8nG4yKSDjgajjgZfjgabjgIFidWZbajEsIGoyXSAobjHooYxuMuWIlykKCQkvLyDlh7rlipvjgavplqLjgZfjgabjga8gaz1uMSprMiArIGsxICgw4ommazHvvJxuMSkg44Go44GX44Gm44CBYnVmW2sxLCBrMl0gKG4x6KGMbjLliJcpCgkJLy8g5Ye65Yqb44Gu6aCG5bqP44Go44Oh44Oi44Oq44Gu44Ki44OJ44Os44K56aCG44KS5ZCI44KP44Gb44KL44Gr44Gv44CBYnVmW2sxLCBrMl3jgpLou6Lnva7jgZfjgaZuMuihjG4x5YiX44Gr44GZ44KL5b+F6KaB44GM44GC44KL44CCCgkJY29uc3QgcG93X3QgdDM2MCA9IChwb3dfdCkxIDw8IHA7CgkJY29uc3QgcG93X3QgbjEgPSAocG93X3QpMSA8PCBleHBuX24xOwoJCWNvbnN0IHBvd190IG4yID0gKHBvd190KTEgPDwgZXhwbl9uMjsKCQljb25zdCBwb3dfdCBuYiA9IChwb3dfdCkxIDw8IGV4cG5fbmI7CgoJCS8vIFNJTuODhuODvOODluODq+eNsuW+lwoJCS8vIOOBk+OBk+OBp+aMh+aVsHDjga7jg4bjg7zjg5bjg6vjgpLnorrkv53jgZfjgabjgYrjgY/jgZPjgajjgafjgIEKCQkvLyDjg57jg6vjg4Hjgrnjg6zjg4Pjg4nlh6bnkIbkuK3jgavjg4bjg7zjg5bjg6vjga5zdGQ6OnZlY3Rvcjo6cmVhbGxvYygp44GM5ZG844Gw44KM44Gq44GP44GX44GmCgkJLy8g5o6S5LuW5Yi25b6h44KS55yB55Wl44Gn44GN44KL44CCCgkJdy5hbGxvY190YWJsZShwKTsKCgkJLy8gNiBzdGVwIGFsZ29yaXRobQojcHJhZ21hIG9tcCBwYXJhbGxlbCBmb3IKCQlmb3IgKHBvd190IEpKID0gMDsgSkogPCBuMjsgSkogKz0gbmIpIHsKCQkJLy8g5L2c5qWt44OQ44OD44OV44Kh5rqW5YKZCgkJCS8vIDLjgpLmjpvjgZHjgabjgYTjgovjga7jga/jgIHlrp/pg6jjgajomZrpg6jjga4y6KaB57Sg44K744OD44OIMeimgee0oOOBp+OBguOCi+OBk+OBqOOBq+OCiOOCi+OAggoJCQkvLyDjgrnjg6zjg4Pjg4nmr47jgavnorrkv53jgZnjgovlv4XopoHjgYzjgYLjgovjgZ/jgoHjgIFwYXJhbGxlbCBmb3Llr77osaHjg5bjg63jg4Pjgq/lhoXjgaflrp/mlr3jgZnjgovjgIIKCQkJc3RkOjp2ZWN0b3I8ZG91YmxlPiB3b3JrKChzaXplX3QpKDIgKiBuYiAqIG4xKSk7CgoJCQkvLyDjgrnjg4jjg6zjg7zjg4jjgarou6Lnva7jgqLjg6vjgrTjg6rjgrrjg6AKCQkJLy8g5q2j5pa56KGM5YiX44Gu6Lui572u44G444Gu5YiG6Kej44GvUEPjgrnjgr/jg7Pjg4njgqLjg63jg7Plrp/ooYzjgavlkJHjgYvjgarjgYTjgZ/jgoHooYzjgo/jgarjgYTjgIIKCQkJZm9yIChwb3dfdCBqID0gSko7IGogPCBKSiArIG5iOyBqKyspIHsKCQkJCWZvciAocG93X3QgaSA9IDA7IGkgPCBuMTsgaSsrKSB7CgkJCQkJLy8g44GT44GT44Gn44GuaeOAgWrjga9qMeOAgWoy44Gr44GC44Gf44KL44CCCgkJCQkJLy8g55u05LiL44Gu5Yem55CG44Gv6Lui572u5Yem55CGCgkJCQkJLy8gICB3b3JrW2oyIC0gSkosIGoxXSA9IGJ1ZltqMSwgajJdCgkJCQkJLy8g44Gr44GC44Gf44KL44CCCgkJCQkJY29uc3QgcG93X3Qgc3JjX2lkeCA9IG4yICogaSArIGo7CgkJCQkJY29uc3QgcG93X3QgZHN0X2lkeCA9IG4xICogKGogLSBKSikgKyBpOwoJCQkJCXdvcmtbMiAqIGRzdF9pZHhdID0gYnVmWzIgKiBzcmNfaWR4XTsJCQkJLy8g5a6f6YOoCgkJCQkJd29ya1syICogZHN0X2lkeCArIDFdID0gYnVmWzIgKiBzcmNfaWR4ICsgMV07CQkvLyDomZrpg6gKCQkJCX0KCQkJfQoKCQkJLy8gU3RlcCAyOiBuYue1hOOBrm4x54K5bXVsdGkgcm93IEZGVAoJCQlmb3IgKHBvd190IGkgPSAwOyBpIDwgbmI7IGkrKykgewoJCQkJLy8g44GT44GT44Gn44GuaeOBr2oyLUpK44Gr5a++5b+c44GZ44KL44CCCgkJCQkvLyDnm7TkuIvjga7lh6bnkIbjga93b3JrW2oyIC0gSkosIGoxXeOBrmox44Gr6Zai44GZ44KL44OV44O844Oq44Ko5aSJ5o+bCgkJCQkvLyAgIHdvcmtbajIgLSBKSiwgazFdID0gzqNbajE9MC4ubjEtMV17IHdvcmtbajIgLSBKSiwgajFdICogKHdfbjEpXihqMSAqIGsxKSB9CgkJCQkvLyAgICAgICAgICAgICAgICAgICAgID0gzqNbajE9MC4ubjEtMV17IGJ1ZltqMSwgajJdICogKHdfbjEpXihqMSAqIGsxKSB9CgkJCQkvLyDjgavjgYLjgZ/jgovjgILjgZPjgZPjgafjgIF3X24x44GvMeOBruWOn+Wni24x5LmX5qC544CCCgkJCQljb25zdCBwb3dfdCByb3dfaGVhZCA9IDIgKiBuMSAqIGk7CgkJCQlmb3VyaV93cnAod29yay5iZWdpbigpICsgcm93X2hlYWQsIGV4cG5fbjEsIHcpOwoJCQl9CgoJCQkvLyBTdGVwIDM6IOOBsuOBreOCiuS/guaVsOOCkuOBi+OBkeOCiwoJCQkvLyBTdGVwIDQ6IOi7oue9rgoJCQlmb3IgKHBvd190IGogPSBKSjsgaiA8IEpKICsgbmI7IGorKykgewoJCQkJZm9yIChwb3dfdCBpID0gMDsgaSA8IG4xOyBpKyspIHsKCQkJCQkvLyDjgZPjgZPjgafjga5p44CBauOBr2sx44CBajLjgavjgYLjgZ/jgovjgIIKCgkJCQkJLy8g6Lui572u44Guc3Jj44GoZHN0CgkJCQkJY29uc3QgcG93X3Qgc3JjX2lkeCA9IG4xICogKGogLSBKSikgKyBpOwkvLyBuMSAqIChqMiAtIEpKKSArIGsxCgkJCQkJY29uc3QgcG93X3QgZHN0X2lkeCA9IG4yICogaSArIGo7CQkJLy8gbjIgKiBrMSArIGoyCgoJCQkJCS8vIOOBsuOBreOCiuS/guaVsCh3X24pXihqMiprMSkKCQkJCQkvLyDjgZPjgZPjgafjgIF3X27jga8x44Gu5Y6f5aeLbuS5l+agueOAggoJCQkJCWRvdWJsZSBvbWdfcmUsIG9tZ19pbTsKCQkJCQl3LnBvdyhwLCBqICogaSwgb21nX3JlLCBvbWdfaW0pOwoKCQkJCQkvLyDjgbLjga3jgorkv4LmlbDjgpLmjpvjgZHjgabou6Lnva4KCQkJCQkvLyDnm7TkuIvjga7lh6bnkIbjga/jgIHjgbLjga3jgorkv4LmlbDjgpLmjpvjgZHjgabou6Lnva7jgZnjgovlh6bnkIYKCQkJCQkvLyAgIGJ1ZltrMSwgajJdID0gd29ya1tqMiAtIEpKLCBrMV0gKiAod19uKV4oajIqazEpCgkJCQkJLy8g44Gr44GC44Gf44KL44CCCgkJCQkJY29uc3QgZG91YmxlIHNyY19yZSA9IHdvcmtbMiAqIHNyY19pZHhdOwoJCQkJCWNvbnN0IGRvdWJsZSBzcmNfaW0gPSB3b3JrWzIgKiBzcmNfaWR4ICsgMV07CgkJCQkJYnVmWzIgKiBkc3RfaWR4XSA9IHNyY19yZSAqIG9tZ19yZSAtIHNyY19pbSAqIG9tZ19pbTsJCQkvLyDlrp/pg6gKCQkJCQlidWZbMiAqIGRzdF9pZHggKyAxXSA9IHNyY19pbSAqIG9tZ19yZSArIHNyY19yZSAqIG9tZ19pbTsJCS8vIOiZmumDqAoJCQkJfQoJCQl9CgkJfQoKCQkvLyBTZXRwIDU6IE4x57WE44GuTjLngrltdWx0aSByb3cgRkZUCgkJLy8g44OW44Ot44OD44KvU2l4LXN0ZXAgYWxnb3JpdGht44Gu5byV55So5YWD44Kz44O844OJ44Gr44KI44KM44GwCgkJLy8gbmLntYTjga5uMueCuW11bHRpIHJvdyBGRlTjgavljLrliIbjgZfjgabooYzjgYbjgbnjgY3jgajjgZPjgo3jgaDjgYzjgIEKCQkvLyBQQ+OCueOCv+ODs+ODieOCouODreODs+Wun+ihjOOBq+WQkeOBi+OBquOBhOOBn+OCgeWMuuWIhuOBl+OBquOBhOOAggojcHJhZ21hIG9tcCBwYXJhbGxlbCBmb3IKCQlmb3IgKHBvd190IGkgPSAwOyBpIDwgbjE7IGkrKykgewoJCQkvLyDjgZPjgZPjgafjga5p44GvazHjgavjgYLjgZ/jgovjgIIKCQkJLy8g55u05LiL44Gu5Yem55CG44Gv44CBYnVmW2sxLCBqMl3jga5qMuOBq+mWouOBmeOCi+ODleODvOODquOCqOWkieaPmwoJCQkvLyAgIGJ1ZltrMSwgazJdID0gzqNbajI9MC4ubjItMV17IGJ1ZltrMSwgajJdICogKHdfbjIpXihqMiAqIGsyKSB9CgkJCS8vIOOBq+OBguOBn+OCi+OAguOBk+OBk+OBp+OAgXdfbjLjga8x44Gu5Y6f5aeLbjLkuZfmoLnjgIIKCQkJY29uc3QgcG93X3Qgcm93X2hlYWQgPSAyICogbjIgKiBpOwoJCQlmb3VyaV93cnAoYnVmICsgcm93X2hlYWQsIGV4cG5fbjIsIHcpOwoKCQkJLy8gU3RlcCA2OiDou6Lnva4KCQkJLy8g5pys5p2l44Gv44OV44O844Oq44Ko5aSJ5o+b57WQ5p6cWChrKeOBjOODoeODouODquS4iuOBp+S4puOBtuOCiOOBhuOBq2J1ZltrMSwgazJd44KSbjLooYzDl24x5YiX44GuMuasoeWFg+mFjeWIl2RzdFssXeOBq+i7oue9ruOBmeOCi+W3peeoi+OBoOOBjOOAgQoJCQkvLyBidWZbTjIgKiBpICsgal0g44KSIFgoTjEgKiBqICsgaSnjgajop6Pph4jjgZnjgovjgZPjgajjgavjgZfjgabnnIHnlaXjgZnjgovjgIIKCQl9Cgl9CgoJLy8vIOODleODvOODquOCqOmAhuWkieaPmwoJLy8vIGJ1Zltd44Go44GX44Gm44Gv44CBZm91cmliNigp44Gu57WQ5p6c44KS6Lui572u44Gb44Ga44Gr44Gd44Gu44G+44G+5LiO44GI44KL5YmN5o+Q44CCCgkvLy8gZXhwbl9uMeOCgmZvdXJpYjYoKeOBq+S4juOBiOOBn+OCguOBruOBqOWQjOOBmOWApOOCkuS4juOBiOOCi+OAggoJdm9pZCBmb3VyaWI2aW52KAoJCXN0ZDo6dmVjdG9yPGRvdWJsZT46Oml0ZXJhdG9yIGJ1ZiwKCQljb25zdCBleHBuX3QgcCwKCQludGhfcm9vdCYgdywKCQljb25zdCBleHBuX3QgZXhwbl9uMSkKCXsKCQkvLyDooYzmlbDjgYzlhajkvZPjga7jgrXjgqTjgrrku6XkuIvjgafjgYLjgovjgZPjgagKCQlpZiAoISgwIDw9IGV4cG5fbjEgJiYgZXhwbl9uMSA8PSBwKSkgewoJCQkvLyDjgZPjgZPjgavmnaXjgZ/jgonlkbzjgbPlh7rjgZflhYPjga7jg5DjgrAKCQkJYWJvcnQoKTsKCQl9CgoJCS8vIOWIl+aVsCgy44Gu5YaqKeOBruaMh+aVsAoJCWNvbnN0IGV4cG5fdCBleHBuX24yID0gcCAtIGV4cG5fbjE7CgoJCS8vIOODluODreODg+OCr+OCteOCpOOCugoJCWNvbnN0IGV4cG5fdCBleHBuX25iID0gZ2V0X2Jlc3RfZXhwbl9uYihleHBuX24yKTsKCgkJLy8gYnVmWzAuLnQzNjAtMV3jgpLopIfntKDmlbDjgpLopoHntKDjgajjgZnjgosy5qyh5YWD6YWN5YiX44Go44G/44Gq44GZ44CCCgkJLy8g5YWl5Yqb44Gr6Zai44GX44Gm44GvIGs9bjEqazIgKyBrMSAoMOKJpmsx77ycbjEpIOOBqOOBl+OBpuOAgWJ1ZltrMSwgazJdIChuMeihjG4y5YiXKQoJCS8vIOWHuuWKm+OBq+mWouOBl+OBpuOBryBqPW4yKmoxICsgajIgKDDiiaZqMu+8nG4yKSDjgajjgZfjgabjgIFidWZbajEsIGoyXSAobjHooYxuMuWIlykKCQkvLyDlhaXlipvjga7poIbluo/jgajjg6Hjg6Ljg6rjga7jgqLjg4njg6zjgrnpoIbjgpLlkIjjgo/jgZvjgovjgavjga/jgIFidWZbazEsIGsyXeOCkui7oue9ruOBl+OBpm4y6KGMbjHliJfjgavjgZnjgovlv4XopoHjgYzjgYLjgovjgYwKCQkvLyDlvZPplqLmlbDjgafjga/jgZ3jga7ou6Lnva7jgpLooYzjgo/jgZrjgavmuIjjgb7jgZvjgovjgIIKCQkvLyDlh7rlipvjga7poIbluo/jgajjg6Hjg6Ljg6rjga7jgqLjg4njg6zjgrnpoIbjga/kuIDoh7TjgZnjgovjgIIKCQljb25zdCBwb3dfdCB0MzYwID0gKHBvd190KTEgPDwgcDsKCQljb25zdCBwb3dfdCBuMSA9IChwb3dfdCkxIDw8IGV4cG5fbjE7CgkJY29uc3QgcG93X3QgbjIgPSAocG93X3QpMSA8PCBleHBuX24yOwoJCWNvbnN0IHBvd190IG5iID0gKHBvd190KTEgPDwgZXhwbl9uYjsKCgkJLy8gU0lO44OG44O844OW44Or542y5b6XCgkJLy8g44GT44GT44Gn5oyH5pWwcOOBruODhuODvOODluODq+OCkueiuuS/neOBl+OBpuOBiuOBj+OBk+OBqOOBp+OAgQoJCS8vIOODnuODq+ODgeOCueODrOODg+ODieWHpueQhuS4reOBq+ODhuODvOODluODq+OBrnN0ZDo6dmVjdG9yOjpyZWFsbG9jKCnjgYzlkbzjgbDjgozjgarjgY/jgZfjgaYKCQkvLyDmjpLku5bliLblvqHjgpLnnIHnlaXjgafjgY3jgovjgIIKCQl3LmFsbG9jX3RhYmxlKHApOwoKCQkvLyBNb2RpZmllZCA2IHN0ZXAgYWxnb3JpdGhtCgkJLy8gU2V0cCAxOiBuMee1hOOBrm4y54K5bXVsdGkgcm93IElGRlQKCQkvLyDjg5bjg63jg4Pjgq9TaXgtc3RlcCBhbGdvcml0aG3jga7lvJXnlKjlhYPjgrPjg7zjg4njgavjgojjgozjgbAKCQkvLyBuYue1hOOBrm4y54K5bXVsdGkgcm93IEZGVOOBq+WMuuWIhuOBl+OBpuihjOOBhuOBueOBjeOBqOOBk+OCjeOBoOOBjOOAgQoJCS8vIFBD44K544K/44Oz44OJ44Ki44Ot44Oz5a6f6KGM44Gr5ZCR44GL44Gq44GE44Gf44KB5Yy65YiG44GX44Gq44GE44CCCiNwcmFnbWEgb21wIHBhcmFsbGVsIGZvcgoJCWZvciAocG93X3QgaSA9IDA7IGkgPCBuMTsgaSsrKSB7CgkJCS8vIOOBk+OBk+OBp+OBrmnjga9rMeOBq+OBguOBn+OCi+OAggoJCQkvLyDnm7TkuIvjga7lh6bnkIbjga9idWZbazEsIGsyXeOBrmsy44Gr6Zai44GZ44KL6YCG44OV44O844Oq44Ko5aSJ5o+bCgkJCS8vICAgYnVmW2sxLCBqMl0gPSAoMS9uMikgKiDOo1trMj0wLi5uMi0xXXsgYnVmW2sxLCBrMl0gKiAod19uMileKC0oajIgKiBrMikpIH0KCQkJLy8g44Gr44GC44Gf44KL44CC44GT44GT44Gn44CBd19uMuOBrzHjga7ljp/lp4tuMuS5l+agueOAggoJCQljb25zdCBwb3dfdCByb3dfaGVhZCA9IDIgKiBuMiAqIGk7CgkJCWZvdXJpaW52X3dycChidWYgKyByb3dfaGVhZCwgZXhwbl9uMiwgdyk7CgkJfQoKCQkvLyBTdGVwIDM6IOOBsuOBreOCiuS/guaVsOOCkuOBi+OBkeOCiwoJCS8vIFN0ZXAgNDog6Lui572uCiNwcmFnbWEgb21wIHBhcmFsbGVsIGZvcgoJCWZvciAocG93X3QgSkogPSAwOyBKSiA8IG4yOyBKSiArPSBuYikgewoJCQkvLyDkvZzmpa3jg5Djg4Pjg5XjgqHmupblgpkKCQkJLy8gMuOCkuaOm+OBkeOBpuOBhOOCi+OBruOBr+OAgeWun+mDqOOBqOiZmumDqOOBrjLopoHntKDjgrvjg4Pjg4gx6KaB57Sg44Gn44GC44KL44GT44Go44Gr44KI44KL44CCCgkJCXN0ZDo6dmVjdG9yPGRvdWJsZT4gd29yaygoc2l6ZV90KSgyICogbmIgKiBuMSkpOwoKCQkJLy8g44K544OI44Os44O844OI44Gq6Lui572u44Ki44Or44K044Oq44K644OgCgkJCS8vIOato+aWueihjOWIl+OBrui7oue9ruOBuOOBruWIhuino+OBr1BD44K544K/44Oz44OJ44Ki44Ot44Oz5a6f6KGM44Gr5ZCR44GL44Gq44GE44Gf44KB6KGM44KP44Gq44GE44CCCgkJCWZvciAocG93X3QgaiA9IEpKOyBqIDwgSkogKyBuYjsgaisrKSB7CgkJCQlmb3IgKHBvd190IGkgPSAwOyBpIDwgbjE7IGkrKykgewoJCQkJCS8vIOOBk+OBk+OBp+OBrmnjgIFq44GvazHjgIFqMuOBq+OBguOBn+OCi+OAggoKCQkJCQkvLyDou6Lnva7jga5zcmPjgahkc3QKCQkJCQljb25zdCBwb3dfdCBzcmNfaWR4ID0gbjIgKiBpICsgajsKCQkJCQljb25zdCBwb3dfdCBkc3RfaWR4ID0gbjEgKiAoaiAtIEpKKSArIGk7CgoJCQkJCS8vIOOBsuOBreOCiuS/guaVsOOBrumAhuaVsCh3X24pXihqMiprMSkKCQkJCQkvLyDjgZPjgZPjgafjgIF3X27jga8x44Gu5Y6f5aeLbuS5l+agueOAggoJCQkJCWRvdWJsZSBvbWdfcmUsIG9tZ19pbTsKCQkJCQl3LnBvdyhwLCBqICogaSwgb21nX3JlLCBvbWdfaW0pOwoKCQkJCQkvLyDjgbLjga3jgorkv4LmlbDjgpLmjpvjgZHjgabou6Lnva4KCQkJCQkvLyDnm7TkuIvjga7lh6bnkIbjga8KCQkJCQkvLyAgIHdvcmtbajIgLSBKSiwgazFdID0gYnVmW2sxLCBqMl0gKiAod19uKV4oLShqMiprMSkpCgkJCQkJLy8g44Gr44GC44Gf44KL44CCCgkJCQkJY29uc3QgZG91YmxlIHNyY19yZSA9IGJ1ZlsyICogc3JjX2lkeF07CgkJCQkJY29uc3QgZG91YmxlIHNyY19pbSA9IGJ1ZlsyICogc3JjX2lkeCArIDFdOwoJCQkJCXdvcmtbMiAqIGRzdF9pZHhdID0gc3JjX3JlICogb21nX3JlICsgc3JjX2ltICogb21nX2ltOwkJCS8vIOWun+mDqAoJCQkJCXdvcmtbMiAqIGRzdF9pZHggKyAxXSA9IHNyY19pbSAqIG9tZ19yZSAtIHNyY19yZSAqIG9tZ19pbTsJCS8vIOiZmumDqAoJCQkJfQoJCQl9CgoJCQkvLyBuYue1hOOBrm4x54K5bXVsdGkgcm93IElGRlQKCQkJZm9yIChwb3dfdCBpID0gMDsgaSA8IG5iOyBpKyspIHsKCQkJCS8vIOOBk+OBk+OBp+OBrmnjga9qMi1KSuOBq+OBguOBn+OCi+OAggoJCQkJLy8g55u05LiL44Gu5Yem55CG44Gv44CBd29ya1tqMiAtIEpKLCBrMV3jga5rMeOBq+mWouOBmeOCi+mAhuODleODvOODquOCqOWkieaPmwoJCQkJLy8gICB3b3JrW2oyIC0gSkosIGoyXSA9ICgxL24xKSAqIM6jW2sxPTAuLm4xLTFdeyB3b3JrW2oyIC0gSkosIGsxXSAqICh3X24xKV4oajEgKiBrMSkgfQoJCQkJLy8gICAgICAgICAgICAgICAgICAgICA9ICgxL24xKSAqIM6jW2sxPTAuLm4xLTFdeyBidWZbazEsIGoyXSAqICh3X24xKV4oajEgKiBrMSkgfQoJCQkJLy8g44Gr44GC44Gf44KL44CC44GT44GT44Gn44CBd19uMeOBrzHjga7ljp/lp4tuMeS5l+agueOAggoJCQkJY29uc3QgcG93X3Qgcm93X2hlYWQgPSAyICogbjEgKiBpOwoJCQkJZm91cmlpbnZfd3JwKHdvcmsuYmVnaW4oKSArIHJvd19oZWFkLCBleHBuX24xLCB3KTsKCQkJfQoKCQkJLy8gSUZGVOe1kOaenOOCkmJ1Zltd44Gu5YWD44Gu5aC05omA44Gr5pu444GN5oi744GZCgkJCS8vIOOCueODiOODrOODvOODiOOBqui7oue9ruOCouODq+OCtOODquOCuuODoAoJCQkvLyDmraPmlrnooYzliJfjga7ou6Lnva7jgbjjga7liIbop6Pjga9QQ+OCueOCv+ODs+ODieOCouODreODs+Wun+ihjOOBq+WQkeOBi+OBquOBhOOBn+OCgeihjOOCj+OBquOBhOOAggoJCQlmb3IgKHBvd190IGogPSBKSjsgaiA8IEpKICsgbmI7IGorKykgewoJCQkJZm9yIChwb3dfdCBpID0gMDsgaSA8IG4xOyBpKyspIHsKCQkJCQkvLyDjgZPjgZPjgafjga5p44CBauOBr2ox44CBajLjgavjgYLjgZ/jgovjgIIKCQkJCQkvLyDnm7TkuIvjga7lh6bnkIbjga/jgIHou6Lnva7lh6bnkIYKCQkJCQkvLyAgIGJ1ZltqMSwgajJdID0gd29ya1tqMiAtIEpKLCBqMV0KCQkJCQkvLyDjgavjgYLjgZ/jgovjgIIKCQkJCQljb25zdCBwb3dfdCBzcmNfaWR4ID0gbjEgKiAoaiAtIEpKKSArIGk7CgkJCQkJY29uc3QgcG93X3QgZHN0X2lkeCA9IG4yICogaSArIGo7CgkJCQkJYnVmWzIgKiBkc3RfaWR4XSA9IHdvcmtbMiAqIHNyY19pZHhdOwkJCQkvLyDlrp/pg6gKCQkJCQlidWZbMiAqIGRzdF9pZHggKyAxXSA9IHdvcmtbMiAqIHNyY19pZHggKyAxXTsJCS8vIOiZmumDqAoJCQkJfQoJCQl9CgkJfQoJfQoKCS8vLyDjg5Xjg7zjg6rjgqjlpInmj5vjga53cmFwcGVyCgl2b2lkIGZvdXJpX3dycCgKCQlzdGQ6OnZlY3Rvcjxkb3VibGU+OjppdGVyYXRvciBidWYsCgkJY29uc3QgZXhwbl90IHAsCgkJbnRoX3Jvb3QmIHcpCgl7CgkJaWYgKHAgPD0gRVhQTl9DQVBBQ0lUWSkgewoJCQkvLyAoRkZU57WQ5p6c44GMTDLjgq3jg6Pjg4Pjgrfjg6XjgrXjgqTjgrrjga7ljYrliIbjgavlj47jgb7jgospCgkJCS8vIOOCueODiOODrOODvOODiOOBq2ZmdOOBmeOCi+OAggoJCQlmZnRuOjpzb3J0X2J5X2J0cihidWYsIHApOwoJCQlmZnRuOjpmb3VyaShidWYsIHAsIHcpOwoJCX0KCQllbHNlIHsKCQkJLy8gKEZGVOe1kOaenOOBjEwy44Kt44Oj44OD44K344Ol44K144Kk44K644Gu5Y2K5YiG44Gr5Y+O44G+44Gq44KJ44GEKQoJCQkvLyBCbG9ja2VkIDYgc3RlcCBhbGdvcml0aG3jgadGRlTjgZnjgosKCQkJLy8gbjEgPSDiiJooMl5wKeOBjOacgOOCguWKueeOh+OBjOiJr+OBhOOBruOBp0VYUE5fQ0FDQUNJVFnjgpLotoXjgYjjgarjgYTnr4Tlm7Ljgafov5HjgYTlgKTjgavjgZnjgovjgIIKCQkJLy8gKDJecCkvbjHjgYxFWFBOX0NBUEFDSVRZ44KS6LaF44GI44KL5aC05ZCI44Gv44CBZm9vdXJpYjYoKeOBi+OCieW9k+mWouaVsOOBq+OBleOCieOBq+WGjeW4sOOBl+OBpue0sOWIhuWMluOBmeOCi+OAggoJCQljb25zdCBpbnQgbjEgPSBzdGQ6Om1pbigocCArIDEpIC8gMiArIDEsIEVYUE5fQ0FQQUNJVFkpOwoJCQkvLyDjg5Xjg7zjg6rjgqjlpInmj5sKCQkJZm91cmliNihidWYsIHAsIHcsIG4xKTsKCQkJLy8g6Lui572uCgkJCWNvbnN0IHBvd190IHQzNjAgPSAocG93X3QpMSA8PCBwOwoJCQlzdGQ6OnZlY3Rvcjxkb3VibGU+IHRtcChidWYsIGJ1ZiArIDIgKiB0MzYwKTsKCQkJdHJhbnNwb3NlKHRtcC5iZWdpbigpLCBidWYsIHAsIG4xKTsKCQl9Cgl9CgoJLy8vIOmAhuODleODvOODquOCqOWkieaPm+OBrndyYXBwZXIKCXZvaWQgZm91cmlpbnZfd3JwKAoJCXN0ZDo6dmVjdG9yPGRvdWJsZT46Oml0ZXJhdG9yIGJ1ZiwKCQljb25zdCBleHBuX3QgcCwKCQludGhfcm9vdCYgdykKCXsKCQlpZiAocCA8PSBFWFBOX0NBUEFDSVRZKSB7CgkJCS8vIChJRkZU57WQ5p6c44GMTDLjgq3jg6Pjg4Pjgrfjg6XjgrXjgqTjgrrjga7ljYrliIbjgavlj47jgb7jgospCgkJCS8vIOOCueODiOODrOODvOODiOOBq2lmZnTjgZnjgovjgIIKCQkJZmZ0bjo6c29ydF9ieV9idHIoYnVmLCBwKTsKCQkJZmZ0bjo6Zm91cmlpbnYoYnVmLCBwLCB3KTsKCQl9CgkJZWxzZSB7CgkJCS8vIChJRkZU57WQ5p6c44GMTDLjgq3jg6Pjg4Pjgrfjg6XjgrXjgqTjgrrjga7ljYrliIbjgavlj47jgb7jgarjgonjgYQpCgkJCS8vIEJsb2NrZWQgNiBzdGVwIGFsZ29yaXRobeOBp0ZGVOOBmeOCiwoJCQkvLyBuMSA9IOKImigyXnAp44GM5pyA44KC5Yq5546H44GM6Imv44GE44Gu44GnRVhQTl9DQUNBQ0lUWeOCkui2heOBiOOBquOBhOevhOWbsuOBp+i/keOBhOWApOOBq+OBmeOCi+OAggoJCQkvLyAoMl5wKS9uMeOBjEVYUE5fQ0FQQUNJVFnjgpLotoXjgYjjgovloLTlkIjjga/jgIFmb291cmliNigp44GL44KJ5b2T6Zai5pWw44Gr44GV44KJ44Gr5YaN5biw44GX44Gm57Sw5YiG5YyW44GZ44KL44CCCgkJCWNvbnN0IGludCBuMSA9IHN0ZDo6bWluKChwICsgMSkgLyAyICsgMSwgRVhQTl9DQVBBQ0lUWSk7CgkJCWNvbnN0IHBvd190IHQzNjAgPSAocG93X3QpMSA8PCBwOwoJCQkvLyDou6Lnva4KCQkJc3RkOjp2ZWN0b3I8ZG91YmxlPiB0bXAoYnVmLCBidWYgKyAoc2l6ZV90KSgyICogdDM2MCkpOwoJCQl0cmFuc3Bvc2UodG1wLmJlZ2luKCksIGJ1ZiwgcCwgbjEpOwoJCQkvLyDpgIbjg5Xjg7zjg6rjgqjlpInmj5sKCQkJZm91cmliNmludihidWYsIHAsIHcsIHAgLSBuMSk7CgkJfQoJfQoKfQkvLyBuYW1lc3BhY2UgZmZ0YjYKCm5hbWVzcGFjZSBmZnRiNl80bgp7Cgl1c2luZyBuYW1lc3BhY2UgcHJpcm9vdDsKCgkvLy8gNG7kuZfmoLnjgavjgojjgovjg5Xjg7zjg6rjgqjlpInmj5soQmxvY2tlZCA2LXN0ZXAgYWxnb3JpdGht54mIKQoJLy8vIHgoaikgKGo9MC4uKDIqdDM2MCktMSnjgYvjgokKCS8vLyAgIHgnKGopID0gKHgoaikgKyBpICogeChqK3QzNjApKSAqIHVeKGovNCkgKGo9MC4udDM2MC0xKQoJLy8vIOOCkuani+aIkOOBl+OAgXgnKGop44KSREZU44GZ44KL44CC44GT44GT44Gn44CBdeOBrzHjga7ljp/lp4soNCAqIG1hZyAqIHQzNjAp5LmX5qC5IChtYWcg4omnIDEp44CCCgl2b2lkIGZvdXJpYjZfNG4oCgkJc3RkOjp2ZWN0b3I8ZG91YmxlPjo6aXRlcmF0b3IgYnVmLAoJCWNvbnN0IGV4cG5fdCBwLAoJCW50aF9yb290JiB3LAoJCWNvbnN0IGV4cG5fdCBleHBuX24xKQoJewoJCWNvbnN0IHBvd190IHQzNjAgPSAocG93X3QpMSA8PCBwOwoKCQl3LmFsbG9jX3RhYmxlKHAgKyAyKTsKCgkJLy8geyB4JyhqKSB95qeL5oiQCgkJLy8geyB4KGopICsgaSAqIHgoait0MzYwKSB9IOOBq3VeKGovNCnjgpLmjpvjgZHjgovjgIIKCQljb25zdCBleHBuX3QgcDIgPSBwICsgMjsKCQlmb3IgKHBvd190IGogPSAwOyBqIDwgdDM2MDsgaisrKSB7CgkJCWNvbnN0IGRvdWJsZSBhID0gYnVmWzIgKiBqXTsKCQkJY29uc3QgZG91YmxlIGIgPSBidWZbMiAqIGogKyAxXTsKCgkJCS8vIHUgPSB3XjTjgajjgZfjgaZ1XihqLzQpID0gd14oaikKCQkJZG91YmxlIHdqX3JlLCB3al9pbTsKCQkJdy5wb3cocDIsIGosIHdqX3JlLCB3al9pbSk7CgkJCWJ1ZlsyICogal0gPSBhICogd2pfcmUgLSBiICogd2pfaW07CgkJCWJ1ZlsyICogaiArIDFdID0gYSAqIHdqX2ltICsgYiAqIHdqX3JlOwoJCX0KCgkJLy8g44OV44O844Oq44Ko5aSJ5o+bCgkJZmZ0YjY6OmZvdXJpYjYoYnVmLCBwLCB3LCBleHBuX24xKTsKCX0KCgkvLy8gNG7kuZfmoLnjgavjgojjgovpgIbjg5Xjg7zjg6rjgqjlpInmj5soQmxvY2tlZCA2LXN0ZXAgYWxnb3JpdGht54mIKQoJdm9pZCBmb3VyaWI2XzRuaW52KAoJCXN0ZDo6dmVjdG9yPGRvdWJsZT46Oml0ZXJhdG9yIGJ1ZiwKCQljb25zdCBleHBuX3QgcCwKCQludGhfcm9vdCYgdywKCQljb25zdCBleHBuX3QgZXhwbl9uMSkKCXsKCQljb25zdCBwb3dfdCB0MzYwID0gKHBvd190KTEgPDwgcDsKCgkJdy5hbGxvY190YWJsZShwICsgMik7CgoJCS8vIOmAhuODleODvOODquOCqOWkieaPmwoJCWZmdGI2Ojpmb3VyaWI2aW52KGJ1ZiwgcCwgdywgZXhwbl9uMSk7CgoJCS8vIHsgeChqKSB95b6p5YWDCgkJY29uc3QgZXhwbl90IHAyID0gcCArIDI7CgkJZm9yIChwb3dfdCBqID0gMDsgaiA8IHQzNjA7IGorKykgewoJCQljb25zdCBkb3VibGUgYSA9IGJ1ZlsyICogal07CgkJCWNvbnN0IGRvdWJsZSBiID0gYnVmWzIgKiBqICsgMV07CgoJCQkvLyB1ID0gd14044Go44GX44GmdV4oLWovNCkgPSB3XigtainjgpLmjpvjgZHjgosKCQkJZG91YmxlIHdqX3JlLCB3al9pbTsKCQkJdy5wb3cocDIsIGosIHdqX3JlLCB3al9pbSk7CgkJCWJ1ZlsyICogal0gPSBhICogd2pfcmUgKyBiICogd2pfaW07CgkJCWJ1ZlsyICogaiArIDFdID0gYiAqIHdqX3JlIC0gYSAqIHdqX2ltOwoJCX0KCX0KCn0JLy8gbmFtZXNwYWNlIGZmdDRuCgpuYW1lc3BhY2Ugb3Blcgp7Cgl1c2luZyBuYW1lc3BhY2UgZmZ0YjZfNG47CgoJc3RydWN0IEkKCXsKCQlzdGQ6OnZlY3RvcjxJX1RZUEU+IGRhdGE7CS8vIOWfuuaVsFJBRElY44Gu5aSa5YCN6ZW344OH44O844K/CgkJc2l6ZV90IG5kaWdpdHM7CQkJCS8vIGRhdGHjgavlhaXjgaPjgabjgYTjgovmnInlirnjgarmoYHmlbAKCgkJSShjb25zdCBzaXplX3QgY2FwKQoJCQk6IGRhdGEoY2FwKSwgbmRpZ2l0cygoc2l6ZV90KTApCgkJewoJCQkvKnBhc3MqLwoJCX0KCX07CgoJc3RydWN0IEYKCXsKCQlzdGQ6OnZlY3Rvcjxkb3VibGU+IGRhdGE7CS8vIOWfuuaVsFstKFJBRElYLzIpLCBSQURJWC8yKeOBruWkmuWAjemVt+ODh+ODvOOCvwoJCWludCBwOwkJCQkJCS8vIDJecCA9PSAoZGF0YeOBruimgee0oOaVsCkg44Go44Gq44KLcAoKCQlGKGNvbnN0IGludCBwXykKCQkJOiBkYXRhKChzaXplX3QpMSA8PCBwXyksIHAoMCkKCQl7CgkJCS8qcGFzcyovCgkJfQoJfTsKCgkvLy8g5pW05pWw44Gu44OV44O844Oq44Ko5aSJ5o+bCgl2b2lkIGkyZihGJiBhLCBjb25zdCBJJiBiLCBjb25zdCBpbnQgcCwgcHJpcm9vdDo6bnRoX3Jvb3QmIHcpCgl7CgkJc2l6ZV90IGk7CgoJCS8vIOasoeaVsDJeKHAtMSkgPSB0MzYw44GuNG7kuZfmoLnjg5Xjg7zjg6rjgqjlpInmj5vjgpLooYzjgYbjgIIKCQkvLyDntZDmnpzjga/lrp/pg6jjgajomZrpg6jjgpLlkIjjgo/jgZvjgaYyXnAgPSAoMiAqIHQzNjAp5qGB5YiG44Go44Gq44KL44CCCgkJY29uc3QgcG93X3QgdDM2MCA9IChwb3dfdCkxIDw8IChwIC0gMSk7CgoJCWFzc2VydChiLm5kaWdpdHMgPD0gKHNpemVfdCl0MzYwKTsKCQlhc3NlcnQoKHNpemVfdCkoMiAqIHQzNjApIDw9IGEuZGF0YS5zaXplKCkpOwoKI2lmZGVmIFNIT1dfSQoJCXByaW50ZigiJXM6IEJlZm9yZSBwcmUgdHIuOlxuIiwgX19GVU5DVElPTl9fKTsKCQlzaG93X3JlX2ltX3NlcShiLmRhdGEsIHApOwojZW5kaWYKCgkJLy8g44OV44O844Oq44Ko5aSJ5o+b44Gu5YmN5Yem55CGCgkJLy8gKGLjgYzooajjgZnmlbTmlbApID0gzqNbaT0wLi5hLm5kaWdpdHMtMV17IGIuZGF0YVtpXSAqIFJBRElYXmkgfSAoMOKJpmIuZGF0YVtpXe+8nFJBRElYKQoJCS8vIOOCkuOAgQoJCS8vIChh44GM6KGo44GZ5pW05pWwKSA9IM6jW2k9MC4uYS5uZGlnaXRzLTFdeyBhLmRhdGFbaV0gKiBSQURJWF5pIH0gKC1SQURJWCAvIDLiiaZhLmRhdGFbaV3vvJxSQURJWCAvIDIpCgkJLy8g44Gr5aSJ5o+b44GZ44KL44CCKGEsIGLjgYzlkIzjgZjmlbTmlbDjgpLooajjgZnjgojjgYbjgavmoYHkuIrjgZLjgoLooYzjgYbjgIIpCgkJYS5wID0gcDsKCQlpbnQgY2FycnkgPSAwOwoJCWZvciAoaSA9IDA7IGkgPCBiLm5kaWdpdHMgLSAxOyBpKyspIHsKCQkJLy8g5a6f6YOo6Jma6YOo6Zqj5o6l5YyWCgkJCS8vIGIuZGF0YVt0MzYwLi5d44KS6Jma6YOo44Gr6YWN572u44GZ44KL44CCCgkJCWNvbnN0IHNpemVfdCBkc3RfaSA9IChpIDwgKHNpemVfdCl0MzYwKSA/IDIgKiBpIDogMiAqIChpIC0gKHNpemVfdCl0MzYwKSArIDE7CgoJCQljb25zdCBpbnQzMl90IHQgPSBiLmRhdGFbaV0gKyBjYXJyeTsJLy8g5qGBW2ld44Gu5YCkCgkJCWlmICh0IDwgKGludDMyX3QpUkFESVggLyAyKSB7CgkJCQkvLyAo5qGBW2ld44Gu5YCk4oiIWzAsIFJBRElYIC8gMikgKQoJCQkJLy8g5L2V44KC44GX44Gq44GECgkJCQlhLmRhdGFbZHN0X2ldID0gdDsKCQkJCWNhcnJ5ID0gMDsKCQkJfQoJCQllbHNlIHsKCQkJCS8vICjmoYFbaV3jga7lgKTiiIhbUkFESVggLyAyLCBSQURJWCkgKQoJCQkJLy8g6KOc5q2j5a6f5pa9CgkJCQkvLyDjgb7jgZrmoYFbaV0gLT0gUkFESVgg44Gr44KI44KK5qGBW2ld44Gu5YCk4oiIWzAsIFJBRElYIC8gMinjgajjgZnjgovjgILjgZ/jgaDjgZcKCQkJCS8vIOOBneOCjOOBoOOBkeOBp+OBryhh44GM6KGo44GZ5pW05pWwKeOBjCBSQURJWCAqIFJBRElYXmkgPSBSQURJWF4oaSsxKeOBoOOBkea4m+OBo+OBpuOBl+OBvuOBhuOBruOBp+OAgQoJCQkJLy8g5rib44Gj44Gf5YiG44KSY2FycnnjgafkuIDjgaTkuIrjga7moYHjgavlm57jgZfjgaboo5zloavjgZnjgovjgIIKCQkJCWEuZGF0YVtkc3RfaV0gPSAoZG91YmxlKSh0IC0gKGludDMyX3QpUkFESVgpOwoJCQkJY2FycnkgPSAxOwoJCQl9CgkJfQoJCXsKCQkJLy8g5a6f6YOo6Jma6YOo6Zqj5o6l5YyWCgkJCWNvbnN0IHNpemVfdCBkc3RfaSA9IChpIDwgKHNpemVfdCl0MzYwKSA/IDIgKiBpIDogMiAqIChpIC0gKHNpemVfdCl0MzYwKSArIDE7CgoJCQkvLyDmnIDkuIrkvY3moYEKCQkJYS5kYXRhW2RzdF9pXSA9IChkb3VibGUpKGIuZGF0YVtpXSArIChJX1RZUEUpY2FycnkpOwoJCQlpKys7CgkJfQoJCWZvciAoOyBpIDwgKHNpemVfdCkoMiAqIHQzNjApOyBpKyspIHsKCQkJLy8g5a6f6YOo6Jma6YOo6Zqj5o6l5YyWCgkJCWNvbnN0IHNpemVfdCBkc3RfaSA9IChpIDwgKHNpemVfdCl0MzYwKSA/IDIgKiBpIDogMiAqIChpIC0gKHNpemVfdCl0MzYwKSArIDE7CgoJCQlhLmRhdGFbZHN0X2ldID0gMC4wOwoJCX0KCiNpZiBkZWZpbmVkKFNIT1dfSVRNKSB8fCBkZWZpbmVkKFNIT1dfSSkKCQlwcmludGYoIkJlZm9yZSBmb3VyaTRuKCk6XG4iKTsKCQlzaG93X3JlX2ltX3NlcShhLmRhdGEsIGEucCk7CiNlbmRpZgoKCQljb25zdCBleHBuX3QgZXhwbl9uMiA9IChwIC0gMSkgLyAyOwoJCWNvbnN0IGV4cG5fdCBleHBuX24xID0gKHAgLSAxKSAtIGV4cG5fbjI7CgoJCS8vIOODleODvOODquOCqOWkieaPm+Wun+aWvQoJCWZmdGI2XzRuOjpmb3VyaWI2XzRuKGEuZGF0YS5iZWdpbigpLCBwIC0gMSwgdywgZXhwbl9uMSk7CgojaWZkZWYgU0hPV19JVE0KCQlwcmludGYoIkFmdGVyIGZvdXJpNG4oKTpcbiIpOwoJCXNob3dfcmVfaW1fc2VxKGEuZGF0YSwgYS5wKTsKI2VuZGlmCgl9CgoJLy8vIOaVtOaVsOOBruODleODvOODquOCqOWkieaPm+e1kOaenOOBruepjSjntZDmnpzjga/mlbTmlbApCgl2b2lkIG11bF9mMmkoSSYgYSwgY29uc3QgRiYgYiwgY29uc3QgRiYgYywgRiYgZCwgZG91YmxlJiBlcnJfbWF4LCBwcmlyb290OjpudGhfcm9vdCYgdykgewoJCWludDY0X3QgY2Fycnk7CgkJc2l6ZV90IGksIHQ7CgoJCWNvbnN0IGludCBwID0gYi5wOwoKCQkvLyDmrKHmlbAyXihwLTEpID0gdDM2MOOBrjRu5LmX5qC544OV44O844Oq44Ko5aSJ5o+b57WQ5p6c44Gu56mN44KS6YCG44OV44O844Oq44Ko5aSJ5o+b44GZ44KL44CCCgkJLy8g57WQ5p6c44Gv5a6f6YOo44Go6Jma6YOo44KS5ZCI44KP44Gb44GmMl5wID0gKDIgKiB0MzYwKeahgeOBqOOBquOCi+OAggoJCWNvbnN0IHBvd190IHQzNjAgPSAoc2l6ZV90KTEgPDwgKHAgLSAxKTsKCgkJYXNzZXJ0KHAgPT0gYy5wKTsKCQlhc3NlcnQoKHNpemVfdCkoMiAqIHQzNjApIDw9IGQuZGF0YS5zaXplKCkpOwoKCQkvLyDnqY0KCQlmb3IgKGkgPSAwOyBpIDwgKHNpemVfdCl0MzYwOyBpKyspIHsKCQkJY29uc3QgZG91YmxlIGJfaV9yZSA9IGIuZGF0YVsyICogaV07CgkJCWNvbnN0IGRvdWJsZSBiX2lfaW0gPSBiLmRhdGFbMiAqIGkgKyAxXTsKCQkJY29uc3QgZG91YmxlIGNfaV9yZSA9IGMuZGF0YVsyICogaV07CgkJCWNvbnN0IGRvdWJsZSBjX2lfaW0gPSBjLmRhdGFbMiAqIGkgKyAxXTsKCgkJCS8vIGRbaV0gPSBiW2ldICogY1tpXQoJCQljb25zdCBkb3VibGUgZF9pX3JlID0gYl9pX3JlICogY19pX3JlIC0gYl9pX2ltICogY19pX2ltOwoJCQljb25zdCBkb3VibGUgZF9pX2ltID0gYl9pX3JlICogY19pX2ltICsgYl9pX2ltICogY19pX3JlOwoJCQlkLmRhdGFbMiAqIGldID0gZF9pX3JlOwoJCQlkLmRhdGFbMiAqIGkgKyAxXSA9IGRfaV9pbTsKCQl9CgojaWZkZWYgU0hPV19JVE0KCQlwcmludGYoIkJlZm9yZSBmb3VyaTRuaW52KCk6XG4iKTsKCQlzaG93X3JlX2ltX3NlcShkLmRhdGEsIGQucCk7CiNlbmRpZgoKCQljb25zdCBleHBuX3QgZXhwbl9uMiA9IChwIC0gMSkgLyAyOwoJCWNvbnN0IGV4cG5fdCBleHBuX24xID0gKHAgLSAxKSAtIGV4cG5fbjI7CgoJCS8vIOmAhuODleODvOODquOCqOWkieaPmwoJCWZmdGI2XzRuOjpmb3VyaWI2XzRuaW52KGQuZGF0YS5iZWdpbigpLCBwIC0gMSwgdywgZXhwbl9uMSk7CgojaWZkZWYgU0hPV19JVE0KCQlwcmludGYoIkFmdGVyIGZvdXJpNG5pbnYoKTpcbiIpOwoJCXNob3dfcmVfaW1fc2VxKGQuZGF0YSwgZC5wKTsKI2VuZGlmCgoJCWNvbnN0IHNpemVfdCBzID0gc3RkOjptaW4oYS5kYXRhLnNpemUoKSwgKHNpemVfdCkoMiAqIHQzNjApKTsKCgkJLy8gQ2FycnkgYW5kIGZpeOWHpueQhgoJCS8vIOOBn+OBoOOBl+WvvuixoeOBqOOBmeOCi+ahgeOBruS4puOBs2QuZGF0YVtd44Gv44CBCgkJLy8g5qGB44Gu5YCk44GMWzAsIFJBRElYKeOBp+OBr+OBquOBj+OAgVstUkFESVggLyAyLCBSQURJWCAvIDIp44Gn44GC44KL44CCCgkJY2FycnkgPSAwOwoJCXQgPSAxOwoJCS8vY29uc3QgZG91YmxlIGsgPSBsZGV4cCgxLjAsIC1wICsgMSk7CQkvLyBrID0gMS4wICogMl4oLXAgKyAxKQoJCWRvdWJsZSBrID0gMS4wOwkJLy8gZm91cmk0bmludigp57WQ5p6c44GvMl5w44Gn5Ymy44KL5b+F6KaB54Sh44GX44CCCgkJZm9yIChpID0gMDsgaSA8IHM7IGkrKykgewoJCQkvLyDlrp/pg6jomZrpg6jpmqPmjqXljJbop6PpmaQKCQkJLy8gYi5kYXRhW3QzNjAuLl3jgpLomZrpg6jjgavphY3nva7jgZnjgovjgIIKCQkJY29uc3Qgc2l6ZV90IHNyY19pID0gKGkgPCAoc2l6ZV90KXQzNjApID8gMiAqIGkgOiAyICogKGkgLSAoc2l6ZV90KXQzNjApICsgMTsKCQkJLy9wcmludGYoInQzNjA9JWxsZCwgcz0lenUsIGk9JXp1LCBzcmNfaT0lenVcbiIsIHQzNjAsIHMsIGksIHNyY19pKTsKCgkJCWNvbnN0IGRvdWJsZSB4ID0gZC5kYXRhW3NyY19pXSAqIGs7CgkJCWludDY0X3QgZSA9IChpbnQ2NF90KWZsb29yKHggKyAwLjUpOwoJCQllcnJfbWF4ID0gc3RkOjptYXgoZXJyX21heCwgZmFicyh4IC0gZSkpOwoJCQllICs9IGNhcnJ5OwoJCQljYXJyeSA9IGUgLyBSQURJWDsKCQkJaW50NjRfdCBmID0gZSAtIGNhcnJ5ICogUkFESVg7CgkJCWlmIChmIDwgMCkgewoJCQkJZiArPSBSQURJWDsKCQkJCWNhcnJ5LS07CgkJCX0KCQkJYS5kYXRhW2ldID0gKElfVFlQRSlmOwoJCQlpZiAoZiAhPSAwKSB7CgkJCQl0ID0gaSArIDE7CgkJCX0KCQl9CgkJYS5uZGlnaXRzID0gdDsKCQlpZiAoY2FycnkgIT0gMCkgewoJCQlpZiAoYS5uZGlnaXRzIDwgYS5kYXRhLnNpemUoKSkgewoJCQkJYXNzZXJ0KDAgPD0gY2FycnkgJiYgY2FycnkgPCBSQURJWCk7CgkJCQlhLmRhdGFbYS5uZGlnaXRzKytdID0gKElfVFlQRSljYXJyeTsKCQkJfQoJCQllbHNlIHsKCQkJCS8vIOOBk+OBk+OBq+adpeOBn+OCieahgeOBguOBteOCjAoJCQkJYWJvcnQoKTsKCQkJfQoJCX0KCQlmb3IgKDsgaSA8IHM7IGkrKykgewoJCQkvLyDlrp/pg6jomZrpg6jpmqPmjqXljJbop6PpmaQKCQkJY29uc3Qgc2l6ZV90IHNyY19pID0gKGkgPCAoc2l6ZV90KXQzNjApID8gMiAqIGkgOiAyICogaSArIDE7CgoJCQljb25zdCBkb3VibGUgeCA9IGQuZGF0YVtzcmNfaV0gKiBrOwoJCQljb25zdCBpbnQ2NF90IGUgPSAoaW50NjRfdClmbG9vcih4ICsgMC41KTsKCQkJZXJyX21heCA9IHN0ZDo6bWF4KGVycl9tYXgsIGZhYnMoeCAtIGUpKTsKCQkJYXNzZXJ0KGUgPT0gMCk7CgkJfQoJfQoKCS8vLyDmlbTmlbDjga7lkowKCXZvaWQgYWRkX2koSSYgYSwgY29uc3QgSSYgYl8sIGNvbnN0IEkmIGNfKSB7CgkJSV9UWVBFIGNhcnJ5LCBkOwoJCXNpemVfdCBpOwoKCQljb25zdCBJJiBiID0gKGJfLm5kaWdpdHMgPiBjXy5uZGlnaXRzKSA/IGNfIDogYl87CS8vIEFsaWFzCgkJY29uc3QgSSYgYyA9IChiXy5uZGlnaXRzID4gY18ubmRpZ2l0cykgPyBiXyA6IGNfOwkvLyBBbGlhcwoJCWFzc2VydChiLm5kaWdpdHMgPD0gYy5uZGlnaXRzKTsKCQlhc3NlcnQoYy5uZGlnaXRzIDw9IGEuZGF0YS5zaXplKCkpOwoKCQljYXJyeSA9IDA7CgkJZm9yIChpID0gMDsgaSA8IGIubmRpZ2l0czsgaSsrKSB7CgkJCWQgPSBiLmRhdGFbaV0gKyBjLmRhdGFbaV0gKyBjYXJyeTsKCQkJY2FycnkgPSAwOwoJCQlpZiAoZCA+PSBSQURJWCkgewoJCQkJZCAtPSBSQURJWDsKCQkJCWNhcnJ5Kys7CgkJCX0KCQkJYS5kYXRhW2ldID0gZDsKCQl9CgkJZm9yICg7IGkgPCBjLm5kaWdpdHM7IGkrKykgewoJCQlkID0gYy5kYXRhW2ldICsgY2Fycnk7CgkJCWNhcnJ5ID0gMDsKCQkJaWYgKGQgPj0gUkFESVgpIHsKCQkJCWQgLT0gUkFESVg7CgkJCQljYXJyeSsrOwoJCQl9CgkJCWEuZGF0YVtpXSA9IGQ7CgkJfQoJCWEubmRpZ2l0cyA9IGMubmRpZ2l0czsKCQlpZiAoYS5uZGlnaXRzIDwgYS5kYXRhLnNpemUoKSkgewoJCQlpZiAoY2FycnkgIT0gMCkgewoJCQkJYS5kYXRhW2EubmRpZ2l0cysrXSA9IGNhcnJ5OwoJCQl9CgkJfQoJCWVsc2UgewoJCQlpZiAoY2FycnkgIT0gMCkgewoJCQkJLy8g44GT44GT44Gr5p2l44Gf44KJ5qGB44GC44G144KMCgkJCQlhYm9ydCgpOwoJCQl9CgkJfQoJfQoKCS8vLyDmlbTmlbDjga7jg5XjgqHjgqTjg6vlh7rlipsKCXZvaWQgcHJpbnQoY29uc3QgY2hhciogY29uc3QgZmlsZW5hbWUsIGNvbnN0IEkmIGEpCgl7CgkJY2hhciBmb3JtYXRbMTBdOwoJCWludCBuUmV0OwoKCQlhc3NlcnQoYS5kYXRhLnNpemUoKSA+IChzaXplX3QpMCk7CgkJYXNzZXJ0KGEubmRpZ2l0cyA8PSBhLmRhdGEuc2l6ZSgpKTsKCgkJRklMRSogZnA7CgkJblJldCA9IGZvcGVuX3Nfd3JwKCZmcCwgZmlsZW5hbWUsICJ3Iik7CgkJaWYgKG5SZXQgIT0gMCkgewoJCQlmZmx1c2goc3Rkb3V0KTsKCQkJZnByaW50ZihzdGRlcnIsICJFUlJPUjogZm9wZW5fc193cnAoKSBmYWlsZWQuIChuUmV0PSVkKVxuIiwgblJldCk7CgkJCWFib3J0KCk7CgkJfQoKCQlzcHJpbnRmX3Nfd3JwKGZvcm1hdCwgX2NvdW50b2YoZm9ybWF0KSwgIiUlMCVkdSIsIEZJRyk7CgoJCXNpemVfdCBzID0gYS5uZGlnaXRzOwoJCWZwcmludGYoZnAsICIlbHUiLCAodW5zaWduZWQgbG9uZylhLmRhdGFbLS1zXSk7CgkJd2hpbGUgKHMgIT0gMCkgewoJCQlmcHJpbnRmKGZwLCBmb3JtYXQsIGEuZGF0YVstLXNdKTsKCQl9CgkJZmNsb3NlKGZwKTsKCX0KCn0JLy8gbmFtZXNwYWNlIG9wZXIKCm5hbWVzcGFjZQp7CgkvLyBOIOKJpyBsb2cyKHMxICogczIp44KS5rqA44Gf44GZ5pyA5bCP44GuTuOCkuaxguOCgeOCi+OAggoJaW50IHMycChjb25zdCBzaXplX3QgczEsIGNvbnN0IHNpemVfdCBzMikgewoJCWludCBpOwoJCWZvciAoaSA9IDE7IGkgPCA2NDsgaSsrKSB7CgkJCWlmICgoKHNpemVfdCkxIDw8IGkpICsgMSA+PSBzMSArIHMyKSB7CgkJCQkvLyAoMl5pICsgMSDiiacgKHMx44Gu5pyJ5Yq55qGB5pWwKSArIChzMuOBruacieWKueahgeaVsCkpCgkJCQlicmVhazsKCQkJfQoJCX0KCQlyZXR1cm4gaTsKCX0KCn0JLy8gbmFtZXNwYWNlCgppbnQgbWFpbigpCnsKCXVzaW5nIG5hbWVzcGFjZSBvcGVyOwoKCWNvbnN0IGludCBuID0gMzQ7CgoJbnRoX3Jvb3QgdzsKCgljb25zdCBpbnQgbWF4X3AgPSBzMnAoKChzaXplX3QpKCgxTExVIDw8IG4pICogbG9nMTAoMikpIC8gRklHICsgMSksIDEpOwoJY29uc3Qgc2l6ZV90IGNhcCA9IChzaXplX3QpMSA8PCBtYXhfcDsKCglJIGEoY2FwKTsKCUYgeChtYXhfcCk7CgoJYS5kYXRhWzBdID0gMTsKCWEubmRpZ2l0cyA9IDE7CgoJZG91YmxlIGVycl9tYXggPSAwLjA7CiNpZmRlZiBTSE9XX0NTTV9USU1FCglzdGQ6OnZlY3Rvcjxkb3VibGU+IGNzbV90aW1lOwoJY29uc3QgZG91YmxlIHN0YXJ0VG1nXzAgPSBvbXBfZ2V0X3d0aW1lKCk7CiNlbmRpZgoJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKI2lmZGVmIFNIT1dfQ1NNX1RJTUUKCQljb25zdCBkb3VibGUgc3RhcnRUbWcgPSBvbXBfZ2V0X3d0aW1lKCk7CiNlbmRpZgoKCQkvLyDlpJrlgI3plbfmlbTmlbB444Gu44OV44O844Oq44Ko5aSJ5o+bCgkJLy8gcCDiiacgbG9nMihhICogYSnjgpLmuoDjgZ/jgZnmnIDlsI/jga5w44KS5rGC44KB44CBCgkJLy8gYeOBruasoeaVsDJecOOBruODleODvOODquOCqOWkieaPm+e1kOaenOOCknjjgavmoLzntI3jgZnjgovjgIIKCQljb25zdCBpbnQgcCA9IHMycChhLm5kaWdpdHMsIGEubmRpZ2l0cyk7CgkJaTJmKHgsIGEsIHAsIHcpOwoKCQkvLyB4ID0geCp444CB44GK44KI44Gz57WQ5p6c44GueOOCkuaVtOaVsOOBq+aIu+OBl+OBpmHjgavmoLzntI3jgZnjgosKCQltdWxfZjJpKGEsIHgsIHgsIHgsIGVycl9tYXgsIHcpOwoJCWFkZF9pKGEsIGEsIGEpOwoKI2lmZGVmIFNIT1dfQ1NNX1RJTUUKCQljb25zdCBkb3VibGUgZW5kVG1nID0gb21wX2dldF93dGltZSgpOwoJCWNzbV90aW1lLnB1c2hfYmFjayhlbmRUbWcgLSBzdGFydFRtZyk7CiNlbmRpZgoKCQkvLyDpgJTkuK3ntYzpgY7lh7rlipsKI2lmZGVmIFNBVkVfSVRNX1JFU1VMVAoJCS8qcGFzcyovCiNlbHNlCgkJaWYgKGkgPj0gbiAtIDEpCiNlbmRpZgoJCXsKCQkJY2hhciBmaWxlbmFtZVsyMDBdOwoJCQlzcHJpbnRmX3Nfd3JwKGZpbGVuYW1lLCBfY291bnRvZihmaWxlbmFtZSksICIlZC50eHQiLCBpICsgMSk7CgkJCXByaW50KGZpbGVuYW1lLCBhKTsKCQl9CgkJcHJpbnRmKCIlZCAlZlxuIiwgaSArIDEsIGVycl9tYXgpOwoJfQojaWZkZWYgU0hPV19DU01fVElNRQoJY29uc3QgZG91YmxlIGVuZFRtZ18wID0gb21wX2dldF93dGltZSgpOwoJcHJpbnRmKCJUb3RhbCB3aXRoIGZpbGUgd3JpdGUgPSAlMTBmIHNlY1xuIiwgZW5kVG1nXzAgLSBzdGFydFRtZ18wKTsKCXByaW50ZigiVG90YWwgb25seSBjb3JlIHRpbWUgID0gJTEwZiBzZWNcbiIsIHN0ZDo6YWNjdW11bGF0ZShjc21fdGltZS5iZWdpbigpLCBjc21fdGltZS5lbmQoKSwgMC4wKSk7Cglmb3IgKHNpemVfdCBpID0gMDsgaSA8IGNzbV90aW1lLnNpemUoKTsgaSsrKSB7CgkJcHJpbnRmKCIyXjJeKCUyenUpICUxMGYgc2VjXG4iLCBpICsgMSwgY3NtX3RpbWVbaV0pOwoJfQojZW5kaWYKCglyZXR1cm4gMDsKfQo=