Ideone.com

fork download

copy

// ランダムフォレスト回帰（random forest regression）by 診断人
// データはhttp://c...content-available-to-author-only...e.com/mathematics/brase/understandable_statistics/7e/students/datasets/mlr/frames/frame.htmlのDenver Neighborhoodsを使用しています。
 
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
 
#define INCMSE (1)			// 重要度INCMSEを使用するか
#define INCNODEPURITY (1)	// 重要度INCNODEPURITYを使用するか
 
using namespace std;
#define SZ(a) ((int)(a).size())
 
 
// 乱数は、xorを使ってますが、メルセンヌツイスターの方がよいかも知れません。
class RandXor
{
public:
	RandXor()
	{
		init();
	}
 
	void init()
	{
		x=123456789;
		y=362436069;
		z=521288629;
		w= 88675123;
	}
 
	inline unsigned int random()
	{
		unsigned int t;
		t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
	}
private:
	unsigned int x;
	unsigned int y;
	unsigned int z;
	unsigned int w;
};
 
static RandXor	randxor;	// マルチスレッド対応にするなら、木ごとに乱数用オブジェクトを用意して、シードを変えましょう。
 
 
typedef double FeatureType;
typedef double AnswerType;
 
struct TreeNode {
	bool leaf;			// 葉（=子がない）ならtrue
	int level;			// ノードの深さ。ルートノードは0
	int featureID;		// 説明変数ID。x0, x1, x2... の0,1,2の部分
	FeatureType value;	// 分割する値
	AnswerType answer;	// ノード内（=領域内）の目的変数yの平均値
	vector <int> bags;	// ノード内（=領域内）に含まれるデータのID
	int left;			// 左側の子のノードID
	int right;			// 右側の子のノードID
#if INCNODEPURITY
	double nodePurity;	// ノードのPurity。平均2乗誤差が入る
#endif // INCNODEPURITY
 
 
	TreeNode() {
		leaf = false;
		level = -1;
		featureID = -1;
		value = 0;
		answer = 0;
		left = -1;
		right = -1;
#if INCNODEPURITY
		nodePurity = 0;
#endif // INCNODEPURITY
	}
};
 
class DecisionTree
{
public:
	DecisionTree() { }
 
	// 学習。訓練データをいれて、決定木を作成する。
	// features 		  説明変数（特徴量）x0,x1,x2...
	// answers			  目的変数y
	// nodeSize			  ノード内に入るデータの数。これを下回れば計算は打ち切られ葉になる。Rの実装では、回帰のときは5、分類のときは1が使われている。
	// maxLevel 		  ノードの深さの最大値
	// numRandomFeatures  領域を分けるときに試す説明変数（グラフでは軸）の数。Rの実装ではmtryという引数で、回帰のときは(説明変数の数)/3、分類のときは(説明変数の数)^0.5が使われている。
	// numRandomPositions 領域を分けるときに試すデータ（グラフでは点）の数
	// rootBagSizeRatio   全訓練データの中から、どれだけの割合をルートに入れるか（ブートストラップサンプリング）
	DecisionTree(const vector <vector <FeatureType> >& features,
		const vector <AnswerType>& answers,
		int nodeSize,
		int maxLevel,
		int numRandomFeatures,
		int numRandomPositions,
		float rootBagSizeRatio)
	{
		const int numData = SZ(features);			// データの数
		const int numFeatures = SZ(features[0]);	// 説明変数の数
		assert(numData == SZ(answers));
		assert(numData>1);
 
#if INCNODEPURITY
		m_incNodePurity.clear();
		m_incNodePurity.resize(numFeatures);
#endif // INCNODEPURITY
 
		TreeNode root;	// ルートのノード
		root.level = 0;
 
		const int rootBagSize = static_cast<int>(numData * rootBagSizeRatio); // ルートに入るデータの数
		root.bags.resize(rootBagSize);
 
#if INCMSE
		vector <int> freq(numData); // データ番号別の、ルートに選ばれた個数
#endif // INCMSE
 
		// ブートストラップサンプリング
		for (int i = 0; i < rootBagSize; i++)
		{
			// ここで、同じIDが選ばれる可能性があるが、問題なし。
			int row = randxor.random() % numData;
			root.bags[i] = row;
#if INCMSE
			freq[row]++;
#endif // INCMSE
		}
 
#if INCMSE
		// 選ばれなかった
		m_oob.clear();
		for (int i = 0; i < SZ(freq); ++i)
		{
			if(freq[i]==0)
			{
				m_oob.emplace_back(i);
			}
		}
#endif // INCMSE
 
#if INCNODEPURITY
		double sumAll = 0; // ルートのyの総和
		for (int p : root.bags)
		{
			sumAll += answers[p];
		}
 
		const double meanAll = sumAll / SZ(root.bags); // ルートのyの平均
		// ルートの平均2乗誤差
		root.nodePurity = 0;
		for (int p : root.bags)
		{
			root.nodePurity += lossFunction(answers[p], meanAll);
		}
#endif // INCNODEPURITY
 
		// 決定木をつくる。m_nodesに子ノードがどんどん追加されていく幅優先探索。
		m_nodes.emplace_back(root);
		int curNode = 0; // 現在の決定木のノード番号
		while (curNode < SZ(m_nodes))
		{
			TreeNode &node = m_nodes[curNode];
 
			// 現在のノードに入っている目的変数が、すべて同じかどうかを調べる
			// （その場合は、ノードを分ける必要がなくなる）
			bool equal = true; // すべて同じならtrue
			for (int i = 1; i<SZ(node.bags); i++)
			{
				if (answers[node.bags[i]] != answers[node.bags[i - 1]])
				{
					equal = false;
					break;
				}
			}
 
			// 葉になる条件のチェック
			if (equal || SZ(node.bags) <= nodeSize || node.level >= maxLevel)
			{
				// 葉にして子ノードは増やさない。
				setLeaf(node, curNode, answers);
				continue;
			}
 
			// どこで分けるのがベストかを調べる
			int bestFeatureID = -1;
			int bestLeft = 0, bestRight = 0;
			FeatureType bestValue = 0;
			double bestMSE = 1e99;	// 平均2乗誤差（平均との差の２乗の和）
#if INCNODEPURITY
			double bestMSELeft = 1e99;	// splitValue未満の平均2乗誤差
			double bestMSERight = 1e99;	// splitValue以上の平均2乗誤差
#endif // INCNODEPURITY
 
			for (int i = 0; i<numRandomFeatures; i++)
			{
				// x0,x1,x2...の、どの軸で分けるかを決める
				int featureID = randxor.random() % numFeatures;
 
 
				for (int j = 0; j<numRandomPositions; j++)	 // どの位置で分けるか
				{
					const int positionID = randxor.random() % SZ(node.bags);
					const FeatureType splitValue = features[node.bags[positionID]][featureID];
					double sumLeft = 0;		// splitValue未満のyの総和
					double sumRight = 0;	// splitValue以上のyの総和
					int totalLeft = 0;		// splitValue未満の個数
					int totalRight = 0;		// splitValue以上の個数
					for (int p : node.bags)
					{
						if (features[p][featureID] < splitValue)
						{
							sumLeft += answers[p];
							totalLeft++;
						}
						else
						{
							sumRight += answers[p];
							totalRight++;
						}
					}
 
					// nodeBagのデータが"未満"か"以上"のどちらかに全部偏ってるので
					// 分け方として意味がないので、すぐやめる。
					if (totalLeft == 0 || totalRight == 0)
						continue;
 
					// 平均との差を使って、平均二乗誤差(MSE)を求める
					double meanLeft = totalLeft == 0 ? 0 : sumLeft / totalLeft;
					double meanRight = totalRight == 0 ? 0 : sumRight / totalRight;
 
					double mseLeft = 0;	// 平均二乗誤差(MSE)
					double mseRight = 0;	// 平均二乗誤差(MSE)
					for (int p : node.bags)
					{
						if (features[p][featureID] < splitValue)
						{
							mseLeft += lossFunction(answers[p], meanLeft);
						}
						else
						{
							mseRight += lossFunction(answers[p], meanRight);
						}
					}
 
					if (mseLeft + mseRight < bestMSE)
					{
						bestMSE = mseLeft + mseRight;
#if INCNODEPURITY
						bestMSELeft = mseLeft;
						bestMSERight = mseRight;
#endif // INCNODEPURITY
						bestValue = splitValue;
						bestFeatureID = featureID;
						bestLeft = totalLeft;
						bestRight = totalRight;
					}
				}
			}
 
			// 左か右にどちらかに偏るような分け方しかできなかった場合は、葉にする
			// （すべての分け方を試すわけではないので、こういうことは起こりえます）
			if (bestLeft == 0 || bestRight == 0)
			{
				setLeaf(node, curNode, answers);
				continue;
			}
 
			// うまく分けれたので、新しい子ノードを２つ追加する
			TreeNode left;
			TreeNode right;
 
			left.level = right.level = node.level + 1;
			node.featureID = bestFeatureID;
			node.value = bestValue;
			node.left = SZ(m_nodes);
			node.right = SZ(m_nodes) + 1;
 
			left.bags.resize(bestLeft);
			right.bags.resize(bestRight);
			for (int p : node.bags)
			{
				if (features[p][node.featureID] < node.value)
				{
					left.bags[--bestLeft] = p;
				}
				else
				{
					right.bags[--bestRight] = p;
				}
			}
 
#if INCNODEPURITY
			left.nodePurity = bestMSELeft;
			right.nodePurity = bestMSERight;
			m_incNodePurity[bestFeatureID] += node.nodePurity - left.nodePurity - right.nodePurity;
#endif // INCNODEPURITY
			m_nodes.emplace_back(left);
			m_nodes.emplace_back(right);
			curNode++;
		}
	}
 
	// 平均との差の2乗を求める
	// y 値
	// mean 平均
	// 返り値	平均との差の2乗
	double lossFunction(double y, double mean) const
	{
		return (y - mean)*(y - mean);
	}
 
	// 予測
	// features テスト用の説明変数x0,x1,x2のセット
	// 返り値	目的変数yの予測値
	AnswerType estimate(const vector <FeatureType>& features) const
	{
		// ルートからたどるだけ
		const TreeNode *pNode = &m_nodes[0];
		while (true)
		{
			if (pNode->leaf)
			{
				break;
			}
 
			const int nextNodeID = features[pNode->featureID] < pNode->value ? pNode->left : pNode->right;
			pNode = &m_nodes[nextNodeID];
		}
 
		return pNode->answer;
	}
 
	// bagsをクリアする。ランダムフォレストで一番メモリを使うのはbagsで、
	// 訓練してしまえばいらないので、メモリ不足のときはクリアしたほうがよい。
	void clearBags()
	{
		for (auto& node : m_nodes)
		{
			node.bags.clear();
			node.bags.shrink_to_fit();
		}
	}
 
	// OOBデータ
	const vector <int>& getOOB() const
	{
		return m_oob;
	}
 
#if INCNODEPURITY
	const vector < double >& getIncNodePurity() const
	{
		return m_incNodePurity;
	}
#endif // INCNODEPURITY
 
private:
 
	// nodeを葉にして、curNodeを次のノードへ進める
	void setLeaf(TreeNode& node, int& curNode, const vector<AnswerType>& answers) const
	{
		node.leaf = true;
 
		// 回帰の場合は、目的変数yの平均を求める
		for (int p : node.bags)
		{
			node.answer += answers[p];
		}
 
		assert(SZ(node.bags) > 0);
		if (SZ(node.bags))
		{
			node.answer /= SZ(node.bags);
		}
		curNode++;
	}
 
	vector < TreeNode > m_nodes;	// 決定木のノードたち。m_nodes[0]がルート
	vector < int > m_oob; // OOBデータ（OOB Examples。訓練データから外れたもの）
#if INCNODEPURITY
	vector < double > m_incNodePurity;
#endif // INCNODEPURITY
};
 
// ランダムフォレスト回帰
class RandomForest {
public:
	RandomForest()
	{
		clear();
	}
 
	// 全部の決定木をクリア
	void clear()
	{
		m_trees.clear();
	}
 
	// 学習。訓練データをいれて、決定木を作成する。
	// 引数は、DecisionTreeにそのまま渡しているだけなので、そちらのコメントを参照してください。
	// numAdditionalTrees 追加する木の数
	void train(const vector <vector <FeatureType> >& features,
		const vector <AnswerType>& answers,
		int nodeSize,
		int maxLevel,
		int numRandomFeatures,
		int numRandomPositions,
		float rootBagSizeRatio,
		int numAdditionalTrees)
	{
		for (int i = 0; i < numAdditionalTrees; i++)
		{
			m_trees.emplace_back(DecisionTree(features, answers, nodeSize, maxLevel, numRandomFeatures, numRandomPositions, rootBagSizeRatio));
		}
	}
 
 
	// 予測
	// features テスト用の説明変数x0,x1,x2のセット
	// 返り値	目的変数yの予測値
	AnswerType estimateRegression(const vector <FeatureType> &testFeatures) const
	{
		if (SZ(m_trees) == 0)
		{
			return 0.0;
		}
 
		// すべての木から得られた結果の平均をとるだけ
		FeatureType sum = 0;
		for (int i = 0; i < SZ(m_trees); i++)
		{
			sum += m_trees[i].estimate(testFeatures);
		}
		return sum / SZ(m_trees);
	}
 
	// 決定木のbagsをクリア（メモリ節約用）
	// treeID 決定木のID
	void clearBags(int treeID)
	{
		m_trees[treeID].clearBags();
	}
 
 
#if INCMSE
 
	// OOBエラーを求める
	// trainingFeatures 	訓練データの説明変数（特徴量）x0,x1,x2...
	// trainingAnswers		訓練データの目的変数y
	// 返り値				OOBエラー
	double calculateOOBErr(const vector <vector <FeatureType> >& trainingFeatures, const vector < AnswerType >& trainingAnswers) const
	{
		const int numFeatures = SZ(trainingFeatures[0]);
		double averageOOBErr = 0.0;
 
		for (int i = 0; i < SZ(m_trees); i++)
		{
			const DecisionTree& tree = m_trees[i];
			double ooberr = 0.0;
 
			// OOBデータを使って、予測。2乗誤差の総和をooberrに入れる。
			const vector <int>& oob = tree.getOOB();
			for (int x = 0; x < SZ(oob); ++x)
			{
				const double myAnswer = tree.estimate(trainingFeatures[oob[x]]);
 
				ooberr += (trainingAnswers[oob[x]] - myAnswer)*(trainingAnswers[oob[x]] - myAnswer);
			}
 
			if(SZ(oob)>0)
			{
				ooberr /= SZ(oob);
			}
 
			averageOOBErr += ooberr;
		}
 
		averageOOBErr /= SZ(m_trees);
 
		return averageOOBErr;
	}
 
	// IncMSEを求める
	// trainingFeatures 	訓練データの説明変数（特徴量）x0,x1,x2...
	// trainingAnswers		訓練データの目的変数y
	// nPerm				特徴量1つあたりのシャッフル予測の回数
	// 返り値				特徴量ごとのIncMSE
	vector <double> calculateIncMSE(const vector <vector <FeatureType> >& trainingFeatures, const vector < AnswerType >& trainingAnswers, int nPerm) const
	{
		const int numFeatures = SZ(trainingFeatures[0]);
		vector <double> errimp(numFeatures);
 
		for (int i = 0; i < SZ(m_trees); i++)
		{
			const DecisionTree& tree = m_trees[i];
			double ooberr = 0.0;
 
			// OOBデータを使って、予測。2乗誤差の総和をooberrに入れる。
			const vector <int>& oob = tree.getOOB();
			for (int x = 0; x < SZ(oob); ++x)
			{
				const double myAnswer = tree.estimate(trainingFeatures[oob[x]]);
				ooberr += (trainingAnswers[oob[x]] - myAnswer)*(trainingAnswers[oob[x]] - myAnswer);
			}
 
			srand(i);
			for (int featureID = 0; featureID < numFeatures; ++featureID) // すべての特徴量featureIDでループ
			{
				double ooberrperm = 0.0;
 
				// OOBデータを、featureID番目の特徴量だけをシャッフル
				vector <FeatureType> swapped(SZ(oob));
				for (int x = 0; x < SZ(oob); ++x)
				{
					swapped[x] = trainingFeatures[oob[x]][featureID];
				}
 
				for (int nploop = 0; nploop < nPerm; ++nploop) // 何回シャッフルしたのを試すか。
				{
					random_shuffle(swapped.begin(), swapped.end());
 
					// すべてのOOBデータでシャッフルしたものを使う
					for (int x = 0; x < SZ(oob); ++x)
					{
						vector <FeatureType> vf(trainingFeatures[oob[x]]);
						vf[featureID] = swapped[x]; // featureID番目の要素だけ差し替え
 
						const double myAnswer = tree.estimate(vf);
						ooberrperm += (trainingAnswers[oob[x]] - myAnswer)*(trainingAnswers[oob[x]] - myAnswer);
					}
				}
 
				const double delta = (ooberrperm / nPerm - ooberr) / SZ(oob);
				errimp[featureID] += delta;
			}
		}
 
		for (int featureID = 0; featureID < numFeatures; ++featureID)
		{
			errimp[featureID] = errimp[featureID] / SZ(m_trees);   //　平均をとる
		}
 
		return errimp;
	}
#endif
 
#if INCNODEPURITY
	// IncNodePurityを求める
	// 返り値				特徴量ごとのIncMSE
	vector <double> calculateIncNodePurity() const
	{
		vector < double > retIncNodePurity;
 
		if (SZ(m_trees) > 0)
		{
			const int numFeatures = SZ(m_trees[0].getIncNodePurity());
			retIncNodePurity.resize(numFeatures);
			for (int i = 0; i < SZ(m_trees); i++)
			{
				const DecisionTree& tree = m_trees[i];
				const vector <double>& purity = tree.getIncNodePurity();
				for (int featureID = 0; featureID < numFeatures; ++featureID)
				{
					retIncNodePurity[featureID] += purity[featureID];
				}
			}
 
			for (int featureID = 0; featureID < numFeatures; ++featureID)
			{
				retIncNodePurity[featureID] /= SZ(m_trees);
			}
		}
 
		return retIncNodePurity;
	}
#endif // INCNODEPURITY
 
private:
	vector < DecisionTree > m_trees;	// たくさんの決定木
};
 
int main()
{
	int numAll; 		// 全データ数
	int numTrainings;	// 訓練データ数
	int numTests;		// テストデータ数
	int numFeatures;	// 説明変数の数
 
	// y = f(x0,x1,x2,...)
	// x0,x1,x2は説明変数です。コード上ではfeatureと命名してます。
	// yは目的変数です。コード上ではanswerという命名をしてます。
 
 
	cin >> numAll >> numTrainings >> numTests >> numFeatures;
	assert(numTrainings+numTests<=numAll);
 
	// 全データ
	vector < vector <FeatureType> > allFeatures(numAll, vector <FeatureType> (numFeatures));
	vector < AnswerType >		allAnswers(numAll);
 
	for(int i = 0 ; i < numAll; ++i)
	{
		for (int k = 0; k < numFeatures; ++k)
		{
			cin >> allFeatures[i][k];
		}
		cin >> allAnswers[i];
	}
 
	// シャッフル用
	vector < int > shuffleTable;
	for (int i = 0; i < numTrainings+numTests; ++i)
	{
		shuffleTable.emplace_back(i);
	}
	random_shuffle(shuffleTable.begin(), shuffleTable.end());
 
	// 訓練データ
	vector < vector <FeatureType> > trainingFeatures(numTrainings, vector <FeatureType>(numFeatures));
	vector < AnswerType >		trainingAnswers(numTrainings);
	for (int i = 0; i < numTrainings; ++i)
	{
		trainingFeatures[i] = allFeatures[shuffleTable[i]];
		trainingAnswers[i]	= allAnswers[shuffleTable[i]];
	}
 
	// テストデータ
	vector < vector <FeatureType> > testFeatures(numTests, vector <FeatureType>(numFeatures));
	vector < AnswerType >		testAnswers(numTests);
	for (int i = 0; i < numTests; ++i)
	{
		testFeatures[i] = allFeatures[shuffleTable[numTrainings+i]];
		testAnswers[i]	= allAnswers[shuffleTable[numTrainings+i]];
	}
 
	// ランダムフォレストを使って予測
	RandomForest* rf = new RandomForest();
 
	// 学習
	const int numTrees = 100;
	rf->train(trainingFeatures, trainingAnswers, 5, 999, 2, 5, 0.66f, numTrees);
 
	// 予測と結果表示
	printf("-----\n");
 
#if INCMSE
	{
		vector <double> vd = rf->calculateIncMSE(trainingFeatures, trainingAnswers, 5);
		for (int i = 0; i < SZ(vd); ++i)
		{
			printf("IncMSE        x%d=%8.2f\n",i,vd[i]);
		}
	}
#endif // INCMSE
 
#if INCNODEPURITY
	{
		vector <double> vd = rf->calculateIncNodePurity();
		for (int i = 0; i < SZ(vd); ++i)
		{
			printf("IncNodePurity x%d=%8.2f\n",i,vd[i]);
		}
	}
#endif // INCNODEPURITY
 
	double totalError = 0.0;
	for (int i = 0; i < numTests; ++i)
	{
		const double myAnswer = rf->estimateRegression(testFeatures[i]);
		const double diff = myAnswer-testAnswers[i];
		totalError += abs(diff);
		printf("Test%3d myAnswer=%8.2f testAnswer=%8.2f diff=%8.2f\n", i, myAnswer, testAnswers[i], diff);
	}
	printf("totalError=%8.2f\n",totalError);
 
 
	delete rf;
 
	return 0;
}

Ly8g44Op44Oz44OA44Og44OV44Kp44Os44K544OI5Zue5biw77yIcmFuZG9tIGZvcmVzdCByZWdyZXNzaW9u77yJYnkg6Ki65pat5Lq6Ci8vIOODh+ODvOOCv+OBr2h0dHA6Ly9jLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5lLmNvbS9tYXRoZW1hdGljcy9icmFzZS91bmRlcnN0YW5kYWJsZV9zdGF0aXN0aWNzLzdlL3N0dWRlbnRzL2RhdGFzZXRzL21sci9mcmFtZXMvZnJhbWUuaHRtbOOBrkRlbnZlciBOZWlnaGJvcmhvb2Rz44KS5L2/55So44GX44Gm44GE44G+44GZ44CCCgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8YXNzZXJ0Lmg+CgojZGVmaW5lIElOQ01TRSAoMSkJCQkvLyDph43opoHluqZJTkNNU0XjgpLkvb/nlKjjgZnjgovjgYsKI2RlZmluZSBJTkNOT0RFUFVSSVRZICgxKQkvLyDph43opoHluqZJTkNOT0RFUFVSSVRZ44KS5L2/55So44GZ44KL44GLCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIFNaKGEpICgoaW50KShhKS5zaXplKCkpCgoKLy8g5Lmx5pWw44Gv44CBeG9y44KS5L2/44Gj44Gm44G+44GZ44GM44CB44Oh44Or44K744Oz44OM44OE44Kk44K544K/44O844Gu5pa544GM44KI44GE44GL44KC55+l44KM44G+44Gb44KT44CCCmNsYXNzIFJhbmRYb3IKewpwdWJsaWM6CglSYW5kWG9yKCkKCXsKCQlpbml0KCk7Cgl9CgoJdm9pZCBpbml0KCkKCXsKCQl4PTEyMzQ1Njc4OTsKCQl5PTM2MjQzNjA2OTsKCQl6PTUyMTI4ODYyOTsKCQl3PSA4ODY3NTEyMzsKCX0KCglpbmxpbmUgdW5zaWduZWQgaW50IHJhbmRvbSgpCgl7CgkJdW5zaWduZWQgaW50IHQ7CgkJdD0oeF4oeDw8MTEpKTt4PXk7eT16O3o9dzsgcmV0dXJuKCB3PSh3Xih3Pj4xOSkpXih0Xih0Pj44KSkgKTsKCX0KcHJpdmF0ZToKCXVuc2lnbmVkIGludCB4OwoJdW5zaWduZWQgaW50IHk7Cgl1bnNpZ25lZCBpbnQgejsKCXVuc2lnbmVkIGludCB3Owp9OwoKc3RhdGljIFJhbmRYb3IJcmFuZHhvcjsJLy8g44Oe44Or44OB44K544Os44OD44OJ5a++5b+c44Gr44GZ44KL44Gq44KJ44CB5pyo44GU44Go44Gr5Lmx5pWw55So44Kq44OW44K444Kn44Kv44OI44KS55So5oSP44GX44Gm44CB44K344O844OJ44KS5aSJ44GI44G+44GX44KH44GG44CCCgoKdHlwZWRlZiBkb3VibGUgRmVhdHVyZVR5cGU7CnR5cGVkZWYgZG91YmxlIEFuc3dlclR5cGU7CgpzdHJ1Y3QgVHJlZU5vZGUgewoJYm9vbCBsZWFmOwkJCS8vIOiRie+8iD3lrZDjgYzjgarjgYTvvInjgarjgol0cnVlCglpbnQgbGV2ZWw7CQkJLy8g44OO44O844OJ44Gu5rex44GV44CC44Or44O844OI44OO44O844OJ44GvMAoJaW50IGZlYXR1cmVJRDsJCS8vIOiqrOaYjuWkieaVsElE44CCeDAsIHgxLCB4Mi4uLiDjga4wLDEsMuOBrumDqOWIhgoJRmVhdHVyZVR5cGUgdmFsdWU7CS8vIOWIhuWJsuOBmeOCi+WApAoJQW5zd2VyVHlwZSBhbnN3ZXI7CS8vIOODjuODvOODieWGhe+8iD3poJjln5/lhoXvvInjga7nm67nmoTlpInmlbB544Gu5bmz5Z2H5YCkCgl2ZWN0b3IgPGludD4gYmFnczsJLy8g44OO44O844OJ5YaF77yIPemgmOWfn+WGhe+8ieOBq+WQq+OBvuOCjOOCi+ODh+ODvOOCv+OBrklECglpbnQgbGVmdDsJCQkvLyDlt6blgbTjga7lrZDjga7jg47jg7zjg4lJRAoJaW50IHJpZ2h0OwkJCS8vIOWPs+WBtOOBruWtkOOBruODjuODvOODiUlECiNpZiBJTkNOT0RFUFVSSVRZCglkb3VibGUgbm9kZVB1cml0eTsJLy8g44OO44O844OJ44GuUHVyaXR544CC5bmz5Z2HMuS5l+iqpOW3ruOBjOWFpeOCiwojZW5kaWYgLy8gSU5DTk9ERVBVUklUWQoKCglUcmVlTm9kZSgpIHsKCQlsZWFmID0gZmFsc2U7CgkJbGV2ZWwgPSAtMTsKCQlmZWF0dXJlSUQgPSAtMTsKCQl2YWx1ZSA9IDA7CgkJYW5zd2VyID0gMDsKCQlsZWZ0ID0gLTE7CgkJcmlnaHQgPSAtMTsKI2lmIElOQ05PREVQVVJJVFkKCQlub2RlUHVyaXR5ID0gMDsKI2VuZGlmIC8vIElOQ05PREVQVVJJVFkKCX0KfTsKCmNsYXNzIERlY2lzaW9uVHJlZQp7CnB1YmxpYzoKCURlY2lzaW9uVHJlZSgpIHsgfQoKCS8vIOWtpue/kuOAguiok+e3tOODh+ODvOOCv+OCkuOBhOOCjOOBpuOAgeaxuuWumuacqOOCkuS9nOaIkOOBmeOCi+OAggoJLy8gZmVhdHVyZXMgCQkgIOiqrOaYjuWkieaVsO+8iOeJueW+tOmHj++8iXgwLHgxLHgyLi4uCgkvLyBhbnN3ZXJzCQkJICDnm67nmoTlpInmlbB5CgkvLyBub2RlU2l6ZQkJCSAg44OO44O844OJ5YaF44Gr5YWl44KL44OH44O844K/44Gu5pWw44CC44GT44KM44KS5LiL5Zue44KM44Gw6KiI566X44Gv5omT44Gh5YiH44KJ44KM6JGJ44Gr44Gq44KL44CCUuOBruWun+ijheOBp+OBr+OAgeWbnuW4sOOBruOBqOOBjeOBrzXjgIHliIbpoZ7jga7jgajjgY3jga8x44GM5L2/44KP44KM44Gm44GE44KL44CCCgkvLyBtYXhMZXZlbCAJCSAg44OO44O844OJ44Gu5rex44GV44Gu5pyA5aSn5YCkCgkvLyBudW1SYW5kb21GZWF0dXJlcyAg6aCY5Z+f44KS5YiG44GR44KL44Go44GN44Gr6Kmm44GZ6Kqs5piO5aSJ5pWw77yI44Kw44Op44OV44Gn44Gv6Lu477yJ44Gu5pWw44CCUuOBruWun+ijheOBp+OBr210cnnjgajjgYTjgYblvJXmlbDjgafjgIHlm57luLDjga7jgajjgY3jga8o6Kqs5piO5aSJ5pWw44Gu5pWwKS8z44CB5YiG6aGe44Gu44Go44GN44GvKOiqrOaYjuWkieaVsOOBruaVsCleMC4144GM5L2/44KP44KM44Gm44GE44KL44CCCgkvLyBudW1SYW5kb21Qb3NpdGlvbnMg6aCY5Z+f44KS5YiG44GR44KL44Go44GN44Gr6Kmm44GZ44OH44O844K/77yI44Kw44Op44OV44Gn44Gv54K577yJ44Gu5pWwCgkvLyByb290QmFnU2l6ZVJhdGlvICAg5YWo6KiT57e044OH44O844K/44Gu5Lit44GL44KJ44CB44Gp44KM44Gg44GR44Gu5Ymy5ZCI44KS44Or44O844OI44Gr5YWl44KM44KL44GL77yI44OW44O844OI44K544OI44Op44OD44OX44K144Oz44OX44Oq44Oz44Kw77yJCglEZWNpc2lvblRyZWUoY29uc3QgdmVjdG9yIDx2ZWN0b3IgPEZlYXR1cmVUeXBlPiA+JiBmZWF0dXJlcywKCQljb25zdCB2ZWN0b3IgPEFuc3dlclR5cGU+JiBhbnN3ZXJzLAoJCWludCBub2RlU2l6ZSwKCQlpbnQgbWF4TGV2ZWwsCgkJaW50IG51bVJhbmRvbUZlYXR1cmVzLAoJCWludCBudW1SYW5kb21Qb3NpdGlvbnMsCgkJZmxvYXQgcm9vdEJhZ1NpemVSYXRpbykKCXsKCQljb25zdCBpbnQgbnVtRGF0YSA9IFNaKGZlYXR1cmVzKTsJCQkvLyDjg4fjg7zjgr/jga7mlbAKCQljb25zdCBpbnQgbnVtRmVhdHVyZXMgPSBTWihmZWF0dXJlc1swXSk7CS8vIOiqrOaYjuWkieaVsOOBruaVsAoJCWFzc2VydChudW1EYXRhID09IFNaKGFuc3dlcnMpKTsKCQlhc3NlcnQobnVtRGF0YT4xKTsKCiNpZiBJTkNOT0RFUFVSSVRZCgkJbV9pbmNOb2RlUHVyaXR5LmNsZWFyKCk7CgkJbV9pbmNOb2RlUHVyaXR5LnJlc2l6ZShudW1GZWF0dXJlcyk7CiNlbmRpZiAvLyBJTkNOT0RFUFVSSVRZCgoJCVRyZWVOb2RlIHJvb3Q7CS8vIOODq+ODvOODiOOBruODjuODvOODiQoJCXJvb3QubGV2ZWwgPSAwOwoKCQljb25zdCBpbnQgcm9vdEJhZ1NpemUgPSBzdGF0aWNfY2FzdDxpbnQ+KG51bURhdGEgKiByb290QmFnU2l6ZVJhdGlvKTsgLy8g44Or44O844OI44Gr5YWl44KL44OH44O844K/44Gu5pWwCgkJcm9vdC5iYWdzLnJlc2l6ZShyb290QmFnU2l6ZSk7CgojaWYgSU5DTVNFCgkJdmVjdG9yIDxpbnQ+IGZyZXEobnVtRGF0YSk7IC8vIOODh+ODvOOCv+eVquWPt+WIpeOBruOAgeODq+ODvOODiOOBq+mBuOOBsOOCjOOBn+WAi+aVsAojZW5kaWYgLy8gSU5DTVNFCgoJCS8vIOODluODvOODiOOCueODiOODqeODg+ODl+OCteODs+ODl+ODquODs+OCsAoJCWZvciAoaW50IGkgPSAwOyBpIDwgcm9vdEJhZ1NpemU7IGkrKykKCQl7CgkJCS8vIOOBk+OBk+OBp+OAgeWQjOOBmElE44GM6YG444Gw44KM44KL5Y+v6IO95oCn44GM44GC44KL44GM44CB5ZWP6aGM44Gq44GX44CCCgkJCWludCByb3cgPSByYW5keG9yLnJhbmRvbSgpICUgbnVtRGF0YTsKCQkJcm9vdC5iYWdzW2ldID0gcm93OwojaWYgSU5DTVNFCgkJCWZyZXFbcm93XSsrOwojZW5kaWYgLy8gSU5DTVNFCgkJfQoKI2lmIElOQ01TRQoJCS8vIOmBuOOBsOOCjOOBquOBi+OBo+OBnwoJCW1fb29iLmNsZWFyKCk7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBTWihmcmVxKTsgKytpKQoJCXsKCQkJaWYoZnJlcVtpXT09MCkKCQkJewoJCQkJbV9vb2IuZW1wbGFjZV9iYWNrKGkpOwoJCQl9CgkJfQojZW5kaWYgLy8gSU5DTVNFCgojaWYgSU5DTk9ERVBVUklUWQoJCWRvdWJsZSBzdW1BbGwgPSAwOyAvLyDjg6vjg7zjg4jjga5544Gu57eP5ZKMCgkJZm9yIChpbnQgcCA6IHJvb3QuYmFncykKCQl7CgkJCXN1bUFsbCArPSBhbnN3ZXJzW3BdOwoJCX0KCgkJY29uc3QgZG91YmxlIG1lYW5BbGwgPSBzdW1BbGwgLyBTWihyb290LmJhZ3MpOyAvLyDjg6vjg7zjg4jjga5544Gu5bmz5Z2HCgkJLy8g44Or44O844OI44Gu5bmz5Z2HMuS5l+iqpOW3rgoJCXJvb3Qubm9kZVB1cml0eSA9IDA7CgkJZm9yIChpbnQgcCA6IHJvb3QuYmFncykKCQl7CgkJCXJvb3Qubm9kZVB1cml0eSArPSBsb3NzRnVuY3Rpb24oYW5zd2Vyc1twXSwgbWVhbkFsbCk7CgkJfQojZW5kaWYgLy8gSU5DTk9ERVBVUklUWQoKCQkvLyDmsbrlrprmnKjjgpLjgaTjgY/jgovjgIJtX25vZGVz44Gr5a2Q44OO44O844OJ44GM44Gp44KT44Gp44KT6L+95Yqg44GV44KM44Gm44GE44GP5bmF5YSq5YWI5o6i57Si44CCCgkJbV9ub2Rlcy5lbXBsYWNlX2JhY2socm9vdCk7CgkJaW50IGN1ck5vZGUgPSAwOyAvLyDnj77lnKjjga7msbrlrprmnKjjga7jg47jg7zjg4nnlarlj7cKCQl3aGlsZSAoY3VyTm9kZSA8IFNaKG1fbm9kZXMpKQoJCXsKCQkJVHJlZU5vZGUgJm5vZGUgPSBtX25vZGVzW2N1ck5vZGVdOwoKCQkJLy8g54++5Zyo44Gu44OO44O844OJ44Gr5YWl44Gj44Gm44GE44KL55uu55qE5aSJ5pWw44GM44CB44GZ44G544Gm5ZCM44GY44GL44Gp44GG44GL44KS6Kq/44G544KLCgkJCS8vIO+8iOOBneOBruWgtOWQiOOBr+OAgeODjuODvOODieOCkuWIhuOBkeOCi+W/heimgeOBjOOBquOBj+OBquOCi++8iQoJCQlib29sIGVxdWFsID0gdHJ1ZTsgLy8g44GZ44G544Gm5ZCM44GY44Gq44KJdHJ1ZQoJCQlmb3IgKGludCBpID0gMTsgaTxTWihub2RlLmJhZ3MpOyBpKyspCgkJCXsKCQkJCWlmIChhbnN3ZXJzW25vZGUuYmFnc1tpXV0gIT0gYW5zd2Vyc1tub2RlLmJhZ3NbaSAtIDFdXSkKCQkJCXsKCQkJCQllcXVhbCA9IGZhbHNlOwoJCQkJCWJyZWFrOwoJCQkJfQoJCQl9CgoJCQkvLyDokYnjgavjgarjgovmnaHku7bjga7jg4Hjgqfjg4Pjgq8KCQkJaWYgKGVxdWFsIHx8IFNaKG5vZGUuYmFncykgPD0gbm9kZVNpemUgfHwgbm9kZS5sZXZlbCA+PSBtYXhMZXZlbCkKCQkJewoJCQkJLy8g6JGJ44Gr44GX44Gm5a2Q44OO44O844OJ44Gv5aKX44KE44GV44Gq44GE44CCCgkJCQlzZXRMZWFmKG5vZGUsIGN1ck5vZGUsIGFuc3dlcnMpOwoJCQkJY29udGludWU7CgkJCX0KCgkJCS8vIOOBqeOBk+OBp+WIhuOBkeOCi+OBruOBjOODmeOCueODiOOBi+OCkuiqv+OBueOCiwoJCQlpbnQgYmVzdEZlYXR1cmVJRCA9IC0xOwoJCQlpbnQgYmVzdExlZnQgPSAwLCBiZXN0UmlnaHQgPSAwOwoJCQlGZWF0dXJlVHlwZSBiZXN0VmFsdWUgPSAwOwoJCQlkb3VibGUgYmVzdE1TRSA9IDFlOTk7CS8vIOW5s+WdhzLkuZfoqqTlt67vvIjlubPlnYfjgajjga7lt67jga7vvJLkuZfjga7lkozvvIkKI2lmIElOQ05PREVQVVJJVFkKCQkJZG91YmxlIGJlc3RNU0VMZWZ0ID0gMWU5OTsJLy8gc3BsaXRWYWx1Zeacqua6gOOBruW5s+WdhzLkuZfoqqTlt64KCQkJZG91YmxlIGJlc3RNU0VSaWdodCA9IDFlOTk7CS8vIHNwbGl0VmFsdWXku6XkuIrjga7lubPlnYcy5LmX6Kqk5beuCiNlbmRpZiAvLyBJTkNOT0RFUFVSSVRZCgoJCQlmb3IgKGludCBpID0gMDsgaTxudW1SYW5kb21GZWF0dXJlczsgaSsrKQoJCQl7CgkJCQkvLyB4MCx4MSx4Mi4uLuOBruOAgeOBqeOBrui7uOOBp+WIhuOBkeOCi+OBi+OCkuaxuuOCgeOCiwoJCQkJaW50IGZlYXR1cmVJRCA9IHJhbmR4b3IucmFuZG9tKCkgJSBudW1GZWF0dXJlczsKCgoJCQkJZm9yIChpbnQgaiA9IDA7IGo8bnVtUmFuZG9tUG9zaXRpb25zOyBqKyspCSAvLyDjganjga7kvY3nva7jgafliIbjgZHjgovjgYsKCQkJCXsKCQkJCQljb25zdCBpbnQgcG9zaXRpb25JRCA9IHJhbmR4b3IucmFuZG9tKCkgJSBTWihub2RlLmJhZ3MpOwoJCQkJCWNvbnN0IEZlYXR1cmVUeXBlIHNwbGl0VmFsdWUgPSBmZWF0dXJlc1tub2RlLmJhZ3NbcG9zaXRpb25JRF1dW2ZlYXR1cmVJRF07CgkJCQkJZG91YmxlIHN1bUxlZnQgPSAwOwkJLy8gc3BsaXRWYWx1Zeacqua6gOOBrnnjga7nt4/lkowKCQkJCQlkb3VibGUgc3VtUmlnaHQgPSAwOwkvLyBzcGxpdFZhbHVl5Lul5LiK44GueeOBrue3j+WSjAoJCQkJCWludCB0b3RhbExlZnQgPSAwOwkJLy8gc3BsaXRWYWx1Zeacqua6gOOBruWAi+aVsAoJCQkJCWludCB0b3RhbFJpZ2h0ID0gMDsJCS8vIHNwbGl0VmFsdWXku6XkuIrjga7lgIvmlbAKCQkJCQlmb3IgKGludCBwIDogbm9kZS5iYWdzKQoJCQkJCXsKCQkJCQkJaWYgKGZlYXR1cmVzW3BdW2ZlYXR1cmVJRF0gPCBzcGxpdFZhbHVlKQoJCQkJCQl7CgkJCQkJCQlzdW1MZWZ0ICs9IGFuc3dlcnNbcF07CgkJCQkJCQl0b3RhbExlZnQrKzsKCQkJCQkJfQoJCQkJCQllbHNlCgkJCQkJCXsKCQkJCQkJCXN1bVJpZ2h0ICs9IGFuc3dlcnNbcF07CgkJCQkJCQl0b3RhbFJpZ2h0Kys7CgkJCQkJCX0KCQkJCQl9CgoJCQkJCS8vIG5vZGVCYWfjga7jg4fjg7zjgr/jgYwi5pyq5rqAIuOBiyLku6XkuIoi44Gu44Gp44Gh44KJ44GL44Gr5YWo6YOo5YGP44Gj44Gm44KL44Gu44GnCgkJCQkJLy8g5YiG44GR5pa544Go44GX44Gm5oSP5ZGz44GM44Gq44GE44Gu44Gn44CB44GZ44GQ44KE44KB44KL44CCCgkJCQkJaWYgKHRvdGFsTGVmdCA9PSAwIHx8IHRvdGFsUmlnaHQgPT0gMCkKCQkJCQkJY29udGludWU7CgoJCQkJCS8vIOW5s+Wdh+OBqOOBruW3ruOCkuS9v+OBo+OBpuOAgeW5s+Wdh+S6jOS5l+iqpOW3rihNU0Up44KS5rGC44KB44KLCgkJCQkJZG91YmxlIG1lYW5MZWZ0ID0gdG90YWxMZWZ0ID09IDAgPyAwIDogc3VtTGVmdCAvIHRvdGFsTGVmdDsKCQkJCQlkb3VibGUgbWVhblJpZ2h0ID0gdG90YWxSaWdodCA9PSAwID8gMCA6IHN1bVJpZ2h0IC8gdG90YWxSaWdodDsKCgkJCQkJZG91YmxlIG1zZUxlZnQgPSAwOwkvLyDlubPlnYfkuozkuZfoqqTlt64oTVNFKQoJCQkJCWRvdWJsZSBtc2VSaWdodCA9IDA7CS8vIOW5s+Wdh+S6jOS5l+iqpOW3rihNU0UpCgkJCQkJZm9yIChpbnQgcCA6IG5vZGUuYmFncykKCQkJCQl7CgkJCQkJCWlmIChmZWF0dXJlc1twXVtmZWF0dXJlSURdIDwgc3BsaXRWYWx1ZSkKCQkJCQkJewoJCQkJCQkJbXNlTGVmdCArPSBsb3NzRnVuY3Rpb24oYW5zd2Vyc1twXSwgbWVhbkxlZnQpOwoJCQkJCQl9CgkJCQkJCWVsc2UKCQkJCQkJewoJCQkJCQkJbXNlUmlnaHQgKz0gbG9zc0Z1bmN0aW9uKGFuc3dlcnNbcF0sIG1lYW5SaWdodCk7CgkJCQkJCX0KCQkJCQl9CgoJCQkJCWlmIChtc2VMZWZ0ICsgbXNlUmlnaHQgPCBiZXN0TVNFKQoJCQkJCXsKCQkJCQkJYmVzdE1TRSA9IG1zZUxlZnQgKyBtc2VSaWdodDsKI2lmIElOQ05PREVQVVJJVFkKCQkJCQkJYmVzdE1TRUxlZnQgPSBtc2VMZWZ0OwoJCQkJCQliZXN0TVNFUmlnaHQgPSBtc2VSaWdodDsKI2VuZGlmIC8vIElOQ05PREVQVVJJVFkKCQkJCQkJYmVzdFZhbHVlID0gc3BsaXRWYWx1ZTsKCQkJCQkJYmVzdEZlYXR1cmVJRCA9IGZlYXR1cmVJRDsKCQkJCQkJYmVzdExlZnQgPSB0b3RhbExlZnQ7CgkJCQkJCWJlc3RSaWdodCA9IHRvdGFsUmlnaHQ7CgkJCQkJfQoJCQkJfQoJCQl9CgoJCQkvLyDlt6bjgYvlj7PjgavjganjgaHjgonjgYvjgavlgY/jgovjgojjgYbjgarliIbjgZHmlrnjgZfjgYvjgafjgY3jgarjgYvjgaPjgZ/loLTlkIjjga/jgIHokYnjgavjgZnjgosKCQkJLy8g77yI44GZ44G544Gm44Gu5YiG44GR5pa544KS6Kmm44GZ44KP44GR44Gn44Gv44Gq44GE44Gu44Gn44CB44GT44GG44GE44GG44GT44Go44Gv6LW344GT44KK44GI44G+44GZ77yJCgkJCWlmIChiZXN0TGVmdCA9PSAwIHx8IGJlc3RSaWdodCA9PSAwKQoJCQl7CgkJCQlzZXRMZWFmKG5vZGUsIGN1ck5vZGUsIGFuc3dlcnMpOwoJCQkJY29udGludWU7CgkJCX0KCgkJCS8vIOOBhuOBvuOBj+WIhuOBkeOCjOOBn+OBruOBp+OAgeaWsOOBl+OBhOWtkOODjuODvOODieOCku+8kuOBpOi/veWKoOOBmeOCiwoJCQlUcmVlTm9kZSBsZWZ0OwoJCQlUcmVlTm9kZSByaWdodDsKCgkJCWxlZnQubGV2ZWwgPSByaWdodC5sZXZlbCA9IG5vZGUubGV2ZWwgKyAxOwoJCQlub2RlLmZlYXR1cmVJRCA9IGJlc3RGZWF0dXJlSUQ7CgkJCW5vZGUudmFsdWUgPSBiZXN0VmFsdWU7CgkJCW5vZGUubGVmdCA9IFNaKG1fbm9kZXMpOwoJCQlub2RlLnJpZ2h0ID0gU1oobV9ub2RlcykgKyAxOwoKCQkJbGVmdC5iYWdzLnJlc2l6ZShiZXN0TGVmdCk7CgkJCXJpZ2h0LmJhZ3MucmVzaXplKGJlc3RSaWdodCk7CgkJCWZvciAoaW50IHAgOiBub2RlLmJhZ3MpCgkJCXsKCQkJCWlmIChmZWF0dXJlc1twXVtub2RlLmZlYXR1cmVJRF0gPCBub2RlLnZhbHVlKQoJCQkJewoJCQkJCWxlZnQuYmFnc1stLWJlc3RMZWZ0XSA9IHA7CgkJCQl9CgkJCQllbHNlCgkJCQl7CgkJCQkJcmlnaHQuYmFnc1stLWJlc3RSaWdodF0gPSBwOwoJCQkJfQoJCQl9CgojaWYgSU5DTk9ERVBVUklUWQoJCQlsZWZ0Lm5vZGVQdXJpdHkgPSBiZXN0TVNFTGVmdDsKCQkJcmlnaHQubm9kZVB1cml0eSA9IGJlc3RNU0VSaWdodDsKCQkJbV9pbmNOb2RlUHVyaXR5W2Jlc3RGZWF0dXJlSURdICs9IG5vZGUubm9kZVB1cml0eSAtIGxlZnQubm9kZVB1cml0eSAtIHJpZ2h0Lm5vZGVQdXJpdHk7CiNlbmRpZiAvLyBJTkNOT0RFUFVSSVRZCgkJCW1fbm9kZXMuZW1wbGFjZV9iYWNrKGxlZnQpOwoJCQltX25vZGVzLmVtcGxhY2VfYmFjayhyaWdodCk7CgkJCWN1ck5vZGUrKzsKCQl9Cgl9CgoJLy8g5bmz5Z2H44Go44Gu5beu44GuMuS5l+OCkuaxguOCgeOCiwoJLy8geSDlgKQKCS8vIG1lYW4g5bmz5Z2HCgkvLyDov5TjgorlgKQJ5bmz5Z2H44Go44Gu5beu44GuMuS5lwoJZG91YmxlIGxvc3NGdW5jdGlvbihkb3VibGUgeSwgZG91YmxlIG1lYW4pIGNvbnN0Cgl7CgkJcmV0dXJuICh5IC0gbWVhbikqKHkgLSBtZWFuKTsKCX0KCgkvLyDkuojmuKwKCS8vIGZlYXR1cmVzIOODhuOCueODiOeUqOOBruiqrOaYjuWkieaVsHgwLHgxLHgy44Gu44K744OD44OICgkvLyDov5TjgorlgKQJ55uu55qE5aSJ5pWweeOBruS6iOa4rOWApAoJQW5zd2VyVHlwZSBlc3RpbWF0ZShjb25zdCB2ZWN0b3IgPEZlYXR1cmVUeXBlPiYgZmVhdHVyZXMpIGNvbnN0Cgl7CgkJLy8g44Or44O844OI44GL44KJ44Gf44Gp44KL44Gg44GRCgkJY29uc3QgVHJlZU5vZGUgKnBOb2RlID0gJm1fbm9kZXNbMF07CgkJd2hpbGUgKHRydWUpCgkJewoJCQlpZiAocE5vZGUtPmxlYWYpCgkJCXsKCQkJCWJyZWFrOwoJCQl9CgoJCQljb25zdCBpbnQgbmV4dE5vZGVJRCA9IGZlYXR1cmVzW3BOb2RlLT5mZWF0dXJlSURdIDwgcE5vZGUtPnZhbHVlID8gcE5vZGUtPmxlZnQgOiBwTm9kZS0+cmlnaHQ7CgkJCXBOb2RlID0gJm1fbm9kZXNbbmV4dE5vZGVJRF07CgkJfQoKCQlyZXR1cm4gcE5vZGUtPmFuc3dlcjsKCX0KCgkvLyBiYWdz44KS44Kv44Oq44Ki44GZ44KL44CC44Op44Oz44OA44Og44OV44Kp44Os44K544OI44Gn5LiA55Wq44Oh44Oi44Oq44KS5L2/44GG44Gu44GvYmFnc+OBp+OAgQoJLy8g6KiT57e044GX44Gm44GX44G+44GI44Gw44GE44KJ44Gq44GE44Gu44Gn44CB44Oh44Oi44Oq5LiN6Laz44Gu44Go44GN44Gv44Kv44Oq44Ki44GX44Gf44G744GG44GM44KI44GE44CCCgl2b2lkIGNsZWFyQmFncygpCgl7CgkJZm9yIChhdXRvJiBub2RlIDogbV9ub2RlcykKCQl7CgkJCW5vZGUuYmFncy5jbGVhcigpOwoJCQlub2RlLmJhZ3Muc2hyaW5rX3RvX2ZpdCgpOwoJCX0KCX0KCgkvLyBPT0Ljg4fjg7zjgr8KCWNvbnN0IHZlY3RvciA8aW50PiYgZ2V0T09CKCkgY29uc3QKCXsKCQlyZXR1cm4gbV9vb2I7Cgl9CgojaWYgSU5DTk9ERVBVUklUWQoJY29uc3QgdmVjdG9yIDwgZG91YmxlID4mIGdldEluY05vZGVQdXJpdHkoKSBjb25zdAoJewoJCXJldHVybiBtX2luY05vZGVQdXJpdHk7Cgl9CiNlbmRpZiAvLyBJTkNOT0RFUFVSSVRZCgpwcml2YXRlOgoKCS8vIG5vZGXjgpLokYnjgavjgZfjgabjgIFjdXJOb2Rl44KS5qyh44Gu44OO44O844OJ44G46YCy44KB44KLCgl2b2lkIHNldExlYWYoVHJlZU5vZGUmIG5vZGUsIGludCYgY3VyTm9kZSwgY29uc3QgdmVjdG9yPEFuc3dlclR5cGU+JiBhbnN3ZXJzKSBjb25zdAoJewoJCW5vZGUubGVhZiA9IHRydWU7CgoJCS8vIOWbnuW4sOOBruWgtOWQiOOBr+OAgeebrueahOWkieaVsHnjga7lubPlnYfjgpLmsYLjgoHjgosKCQlmb3IgKGludCBwIDogbm9kZS5iYWdzKQoJCXsKCQkJbm9kZS5hbnN3ZXIgKz0gYW5zd2Vyc1twXTsKCQl9CgoJCWFzc2VydChTWihub2RlLmJhZ3MpID4gMCk7CgkJaWYgKFNaKG5vZGUuYmFncykpCgkJewoJCQlub2RlLmFuc3dlciAvPSBTWihub2RlLmJhZ3MpOwoJCX0KCQljdXJOb2RlKys7Cgl9CgoJdmVjdG9yIDwgVHJlZU5vZGUgPiBtX25vZGVzOwkvLyDmsbrlrprmnKjjga7jg47jg7zjg4njgZ/jgaHjgIJtX25vZGVzWzBd44GM44Or44O844OICgl2ZWN0b3IgPCBpbnQgPiBtX29vYjsgLy8gT09C44OH44O844K/77yIT09CIEV4YW1wbGVz44CC6KiT57e044OH44O844K/44GL44KJ5aSW44KM44Gf44KC44Gu77yJCiNpZiBJTkNOT0RFUFVSSVRZCgl2ZWN0b3IgPCBkb3VibGUgPiBtX2luY05vZGVQdXJpdHk7CiNlbmRpZiAvLyBJTkNOT0RFUFVSSVRZCn07CgovLyDjg6njg7Pjg4Djg6Djg5Xjgqnjg6zjgrnjg4jlm57luLAKY2xhc3MgUmFuZG9tRm9yZXN0IHsKcHVibGljOgoJUmFuZG9tRm9yZXN0KCkKCXsKCQljbGVhcigpOwoJfQoKCS8vIOWFqOmDqOOBruaxuuWumuacqOOCkuOCr+ODquOCogoJdm9pZCBjbGVhcigpCgl7CgkJbV90cmVlcy5jbGVhcigpOwoJfQoKCS8vIOWtpue/kuOAguiok+e3tOODh+ODvOOCv+OCkuOBhOOCjOOBpuOAgeaxuuWumuacqOOCkuS9nOaIkOOBmeOCi+OAggoJLy8g5byV5pWw44Gv44CBRGVjaXNpb25UcmVl44Gr44Gd44Gu44G+44G+5rih44GX44Gm44GE44KL44Gg44GR44Gq44Gu44Gn44CB44Gd44Gh44KJ44Gu44Kz44Oh44Oz44OI44KS5Y+C54Wn44GX44Gm44GP44Gg44GV44GE44CCCgkvLyBudW1BZGRpdGlvbmFsVHJlZXMg6L+95Yqg44GZ44KL5pyo44Gu5pWwCgl2b2lkIHRyYWluKGNvbnN0IHZlY3RvciA8dmVjdG9yIDxGZWF0dXJlVHlwZT4gPiYgZmVhdHVyZXMsCgkJY29uc3QgdmVjdG9yIDxBbnN3ZXJUeXBlPiYgYW5zd2VycywKCQlpbnQgbm9kZVNpemUsCgkJaW50IG1heExldmVsLAoJCWludCBudW1SYW5kb21GZWF0dXJlcywKCQlpbnQgbnVtUmFuZG9tUG9zaXRpb25zLAoJCWZsb2F0IHJvb3RCYWdTaXplUmF0aW8sCgkJaW50IG51bUFkZGl0aW9uYWxUcmVlcykKCXsKCQlmb3IgKGludCBpID0gMDsgaSA8IG51bUFkZGl0aW9uYWxUcmVlczsgaSsrKQoJCXsKCQkJbV90cmVlcy5lbXBsYWNlX2JhY2soRGVjaXNpb25UcmVlKGZlYXR1cmVzLCBhbnN3ZXJzLCBub2RlU2l6ZSwgbWF4TGV2ZWwsIG51bVJhbmRvbUZlYXR1cmVzLCBudW1SYW5kb21Qb3NpdGlvbnMsIHJvb3RCYWdTaXplUmF0aW8pKTsKCQl9Cgl9CgoKCS8vIOS6iOa4rAoJLy8gZmVhdHVyZXMg44OG44K544OI55So44Gu6Kqs5piO5aSJ5pWweDAseDEseDLjga7jgrvjg4Pjg4gKCS8vIOi/lOOCiuWApAnnm67nmoTlpInmlbB544Gu5LqI5ris5YCkCglBbnN3ZXJUeXBlIGVzdGltYXRlUmVncmVzc2lvbihjb25zdCB2ZWN0b3IgPEZlYXR1cmVUeXBlPiAmdGVzdEZlYXR1cmVzKSBjb25zdAoJewoJCWlmIChTWihtX3RyZWVzKSA9PSAwKQoJCXsKCQkJcmV0dXJuIDAuMDsKCQl9CgoJCS8vIOOBmeOBueOBpuOBruacqOOBi+OCieW+l+OCieOCjOOBn+e1kOaenOOBruW5s+Wdh+OCkuOBqOOCi+OBoOOBkQoJCUZlYXR1cmVUeXBlIHN1bSA9IDA7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBTWihtX3RyZWVzKTsgaSsrKQoJCXsKCQkJc3VtICs9IG1fdHJlZXNbaV0uZXN0aW1hdGUodGVzdEZlYXR1cmVzKTsKCQl9CgkJcmV0dXJuIHN1bSAvIFNaKG1fdHJlZXMpOwoJfQoKCS8vIOaxuuWumuacqOOBrmJhZ3PjgpLjgq/jg6rjgqLvvIjjg6Hjg6Ljg6rnr4DntITnlKjvvIkKCS8vIHRyZWVJRCDmsbrlrprmnKjjga5JRAoJdm9pZCBjbGVhckJhZ3MoaW50IHRyZWVJRCkKCXsKCQltX3RyZWVzW3RyZWVJRF0uY2xlYXJCYWdzKCk7Cgl9CgoKI2lmIElOQ01TRQoKCS8vIE9PQuOCqOODqeODvOOCkuaxguOCgeOCiwoJLy8gdHJhaW5pbmdGZWF0dXJlcyAJ6KiT57e044OH44O844K/44Gu6Kqs5piO5aSJ5pWw77yI54m55b606YeP77yJeDAseDEseDIuLi4KCS8vIHRyYWluaW5nQW5zd2VycwkJ6KiT57e044OH44O844K/44Gu55uu55qE5aSJ5pWweQoJLy8g6L+U44KK5YCkCQkJCU9PQuOCqOODqeODvAoJZG91YmxlIGNhbGN1bGF0ZU9PQkVycihjb25zdCB2ZWN0b3IgPHZlY3RvciA8RmVhdHVyZVR5cGU+ID4mIHRyYWluaW5nRmVhdHVyZXMsIGNvbnN0IHZlY3RvciA8IEFuc3dlclR5cGUgPiYgdHJhaW5pbmdBbnN3ZXJzKSBjb25zdAoJewoJCWNvbnN0IGludCBudW1GZWF0dXJlcyA9IFNaKHRyYWluaW5nRmVhdHVyZXNbMF0pOwoJCWRvdWJsZSBhdmVyYWdlT09CRXJyID0gMC4wOwoKCQlmb3IgKGludCBpID0gMDsgaSA8IFNaKG1fdHJlZXMpOyBpKyspCgkJewoJCQljb25zdCBEZWNpc2lvblRyZWUmIHRyZWUgPSBtX3RyZWVzW2ldOwoJCQlkb3VibGUgb29iZXJyID0gMC4wOwoKCQkJLy8gT09C44OH44O844K/44KS5L2/44Gj44Gm44CB5LqI5ris44CCMuS5l+iqpOW3ruOBrue3j+WSjOOCkm9vYmVycuOBq+WFpeOCjOOCi+OAggoJCQljb25zdCB2ZWN0b3IgPGludD4mIG9vYiA9IHRyZWUuZ2V0T09CKCk7CgkJCWZvciAoaW50IHggPSAwOyB4IDwgU1oob29iKTsgKyt4KQoJCQl7CgkJCQljb25zdCBkb3VibGUgbXlBbnN3ZXIgPSB0cmVlLmVzdGltYXRlKHRyYWluaW5nRmVhdHVyZXNbb29iW3hdXSk7CgoJCQkJb29iZXJyICs9ICh0cmFpbmluZ0Fuc3dlcnNbb29iW3hdXSAtIG15QW5zd2VyKSoodHJhaW5pbmdBbnN3ZXJzW29vYlt4XV0gLSBteUFuc3dlcik7CgkJCX0KCgkJCWlmKFNaKG9vYik+MCkKCQkJewoJCQkJb29iZXJyIC89IFNaKG9vYik7CgkJCX0KCgkJCWF2ZXJhZ2VPT0JFcnIgKz0gb29iZXJyOwoJCX0KCgkJYXZlcmFnZU9PQkVyciAvPSBTWihtX3RyZWVzKTsKCgkJcmV0dXJuIGF2ZXJhZ2VPT0JFcnI7Cgl9CgoJLy8gSW5jTVNF44KS5rGC44KB44KLCgkvLyB0cmFpbmluZ0ZlYXR1cmVzIAnoqJPnt7Tjg4fjg7zjgr/jga7oqqzmmI7lpInmlbDvvIjnibnlvrTph4/vvIl4MCx4MSx4Mi4uLgoJLy8gdHJhaW5pbmdBbnN3ZXJzCQnoqJPnt7Tjg4fjg7zjgr/jga7nm67nmoTlpInmlbB5CgkvLyBuUGVybQkJCQnnibnlvrTph48x44Gk44GC44Gf44KK44Gu44K344Oj44OD44OV44Or5LqI5ris44Gu5Zue5pWwCgkvLyDov5TjgorlgKQJCQkJ54m55b606YeP44GU44Go44GuSW5jTVNFCgl2ZWN0b3IgPGRvdWJsZT4gY2FsY3VsYXRlSW5jTVNFKGNvbnN0IHZlY3RvciA8dmVjdG9yIDxGZWF0dXJlVHlwZT4gPiYgdHJhaW5pbmdGZWF0dXJlcywgY29uc3QgdmVjdG9yIDwgQW5zd2VyVHlwZSA+JiB0cmFpbmluZ0Fuc3dlcnMsIGludCBuUGVybSkgY29uc3QKCXsKCQljb25zdCBpbnQgbnVtRmVhdHVyZXMgPSBTWih0cmFpbmluZ0ZlYXR1cmVzWzBdKTsKCQl2ZWN0b3IgPGRvdWJsZT4gZXJyaW1wKG51bUZlYXR1cmVzKTsKCgkJZm9yIChpbnQgaSA9IDA7IGkgPCBTWihtX3RyZWVzKTsgaSsrKQoJCXsKCQkJY29uc3QgRGVjaXNpb25UcmVlJiB0cmVlID0gbV90cmVlc1tpXTsKCQkJZG91YmxlIG9vYmVyciA9IDAuMDsKCgkJCS8vIE9PQuODh+ODvOOCv+OCkuS9v+OBo+OBpuOAgeS6iOa4rOOAgjLkuZfoqqTlt67jga7nt4/lkozjgpJvb2JlcnLjgavlhaXjgozjgovjgIIKCQkJY29uc3QgdmVjdG9yIDxpbnQ+JiBvb2IgPSB0cmVlLmdldE9PQigpOwoJCQlmb3IgKGludCB4ID0gMDsgeCA8IFNaKG9vYik7ICsreCkKCQkJewoJCQkJY29uc3QgZG91YmxlIG15QW5zd2VyID0gdHJlZS5lc3RpbWF0ZSh0cmFpbmluZ0ZlYXR1cmVzW29vYlt4XV0pOwoJCQkJb29iZXJyICs9ICh0cmFpbmluZ0Fuc3dlcnNbb29iW3hdXSAtIG15QW5zd2VyKSoodHJhaW5pbmdBbnN3ZXJzW29vYlt4XV0gLSBteUFuc3dlcik7CgkJCX0KCgkJCXNyYW5kKGkpOwoJCQlmb3IgKGludCBmZWF0dXJlSUQgPSAwOyBmZWF0dXJlSUQgPCBudW1GZWF0dXJlczsgKytmZWF0dXJlSUQpIC8vIOOBmeOBueOBpuOBrueJueW+tOmHj2ZlYXR1cmVJROOBp+ODq+ODvOODlwoJCQl7CgkJCQlkb3VibGUgb29iZXJycGVybSA9IDAuMDsKCgkJCQkvLyBPT0Ljg4fjg7zjgr/jgpLjgIFmZWF0dXJlSUTnlarnm67jga7nibnlvrTph4/jgaDjgZHjgpLjgrfjg6Pjg4Pjg5Xjg6sKCQkJCXZlY3RvciA8RmVhdHVyZVR5cGU+IHN3YXBwZWQoU1oob29iKSk7CgkJCQlmb3IgKGludCB4ID0gMDsgeCA8IFNaKG9vYik7ICsreCkKCQkJCXsKCQkJCQlzd2FwcGVkW3hdID0gdHJhaW5pbmdGZWF0dXJlc1tvb2JbeF1dW2ZlYXR1cmVJRF07CgkJCQl9CgoJCQkJZm9yIChpbnQgbnBsb29wID0gMDsgbnBsb29wIDwgblBlcm07ICsrbnBsb29wKSAvLyDkvZXlm57jgrfjg6Pjg4Pjg5Xjg6vjgZfjgZ/jga7jgpLoqabjgZnjgYvjgIIKCQkJCXsKCQkJCQlyYW5kb21fc2h1ZmZsZShzd2FwcGVkLmJlZ2luKCksIHN3YXBwZWQuZW5kKCkpOwoKCQkJCQkvLyDjgZnjgbnjgabjga5PT0Ljg4fjg7zjgr/jgafjgrfjg6Pjg4Pjg5Xjg6vjgZfjgZ/jgoLjga7jgpLkvb/jgYYKCQkJCQlmb3IgKGludCB4ID0gMDsgeCA8IFNaKG9vYik7ICsreCkKCQkJCQl7CgkJCQkJCXZlY3RvciA8RmVhdHVyZVR5cGU+IHZmKHRyYWluaW5nRmVhdHVyZXNbb29iW3hdXSk7CgkJCQkJCXZmW2ZlYXR1cmVJRF0gPSBzd2FwcGVkW3hdOyAvLyBmZWF0dXJlSUTnlarnm67jga7opoHntKDjgaDjgZHlt67jgZfmm7/jgYgKCgkJCQkJCWNvbnN0IGRvdWJsZSBteUFuc3dlciA9IHRyZWUuZXN0aW1hdGUodmYpOwoJCQkJCQlvb2JlcnJwZXJtICs9ICh0cmFpbmluZ0Fuc3dlcnNbb29iW3hdXSAtIG15QW5zd2VyKSoodHJhaW5pbmdBbnN3ZXJzW29vYlt4XV0gLSBteUFuc3dlcik7CgkJCQkJfQoJCQkJfQoKCQkJCWNvbnN0IGRvdWJsZSBkZWx0YSA9IChvb2JlcnJwZXJtIC8gblBlcm0gLSBvb2JlcnIpIC8gU1oob29iKTsKCQkJCWVycmltcFtmZWF0dXJlSURdICs9IGRlbHRhOwoJCQl9CgkJfQoKCQlmb3IgKGludCBmZWF0dXJlSUQgPSAwOyBmZWF0dXJlSUQgPCBudW1GZWF0dXJlczsgKytmZWF0dXJlSUQpCgkJewoJCQllcnJpbXBbZmVhdHVyZUlEXSA9IGVycmltcFtmZWF0dXJlSURdIC8gU1oobV90cmVlcyk7ICAgLy/jgIDlubPlnYfjgpLjgajjgosKCQl9CgoJCXJldHVybiBlcnJpbXA7Cgl9CiNlbmRpZgoKI2lmIElOQ05PREVQVVJJVFkKCS8vIEluY05vZGVQdXJpdHnjgpLmsYLjgoHjgosKCS8vIOi/lOOCiuWApAkJCQnnibnlvrTph4/jgZTjgajjga5JbmNNU0UKCXZlY3RvciA8ZG91YmxlPiBjYWxjdWxhdGVJbmNOb2RlUHVyaXR5KCkgY29uc3QKCXsKCQl2ZWN0b3IgPCBkb3VibGUgPiByZXRJbmNOb2RlUHVyaXR5OwoKCQlpZiAoU1oobV90cmVlcykgPiAwKQoJCXsKCQkJY29uc3QgaW50IG51bUZlYXR1cmVzID0gU1oobV90cmVlc1swXS5nZXRJbmNOb2RlUHVyaXR5KCkpOwoJCQlyZXRJbmNOb2RlUHVyaXR5LnJlc2l6ZShudW1GZWF0dXJlcyk7CgkJCWZvciAoaW50IGkgPSAwOyBpIDwgU1oobV90cmVlcyk7IGkrKykKCQkJewoJCQkJY29uc3QgRGVjaXNpb25UcmVlJiB0cmVlID0gbV90cmVlc1tpXTsKCQkJCWNvbnN0IHZlY3RvciA8ZG91YmxlPiYgcHVyaXR5ID0gdHJlZS5nZXRJbmNOb2RlUHVyaXR5KCk7CgkJCQlmb3IgKGludCBmZWF0dXJlSUQgPSAwOyBmZWF0dXJlSUQgPCBudW1GZWF0dXJlczsgKytmZWF0dXJlSUQpCgkJCQl7CgkJCQkJcmV0SW5jTm9kZVB1cml0eVtmZWF0dXJlSURdICs9IHB1cml0eVtmZWF0dXJlSURdOwoJCQkJfQoJCQl9CgoJCQlmb3IgKGludCBmZWF0dXJlSUQgPSAwOyBmZWF0dXJlSUQgPCBudW1GZWF0dXJlczsgKytmZWF0dXJlSUQpCgkJCXsKCQkJCXJldEluY05vZGVQdXJpdHlbZmVhdHVyZUlEXSAvPSBTWihtX3RyZWVzKTsKCQkJfQoJCX0KCgkJcmV0dXJuIHJldEluY05vZGVQdXJpdHk7Cgl9CiNlbmRpZiAvLyBJTkNOT0RFUFVSSVRZCgpwcml2YXRlOgoJdmVjdG9yIDwgRGVjaXNpb25UcmVlID4gbV90cmVlczsJLy8g44Gf44GP44GV44KT44Gu5rG65a6a5pyoCn07CgppbnQgbWFpbigpCnsKCWludCBudW1BbGw7IAkJLy8g5YWo44OH44O844K/5pWwCglpbnQgbnVtVHJhaW5pbmdzOwkvLyDoqJPnt7Tjg4fjg7zjgr/mlbAKCWludCBudW1UZXN0czsJCS8vIOODhuOCueODiOODh+ODvOOCv+aVsAoJaW50IG51bUZlYXR1cmVzOwkvLyDoqqzmmI7lpInmlbDjga7mlbAKCgkvLyB5ID0gZih4MCx4MSx4MiwuLi4pCgkvLyB4MCx4MSx4MuOBr+iqrOaYjuWkieaVsOOBp+OBmeOAguOCs+ODvOODieS4iuOBp+OBr2ZlYXR1cmXjgajlkb3lkI3jgZfjgabjgb7jgZnjgIIKCS8vIHnjga/nm67nmoTlpInmlbDjgafjgZnjgILjgrPjg7zjg4nkuIrjgafjga9hbnN3ZXLjgajjgYTjgYblkb3lkI3jgpLjgZfjgabjgb7jgZnjgIIKCgoJY2luID4+IG51bUFsbCA+PiBudW1UcmFpbmluZ3MgPj4gbnVtVGVzdHMgPj4gbnVtRmVhdHVyZXM7Cglhc3NlcnQobnVtVHJhaW5pbmdzK251bVRlc3RzPD1udW1BbGwpOwoKCS8vIOWFqOODh+ODvOOCvwoJdmVjdG9yIDwgdmVjdG9yIDxGZWF0dXJlVHlwZT4gPiBhbGxGZWF0dXJlcyhudW1BbGwsIHZlY3RvciA8RmVhdHVyZVR5cGU+IChudW1GZWF0dXJlcykpOwoJdmVjdG9yIDwgQW5zd2VyVHlwZSA+CQlhbGxBbnN3ZXJzKG51bUFsbCk7CgoJZm9yKGludCBpID0gMCA7IGkgPCBudW1BbGw7ICsraSkKCXsKCQlmb3IgKGludCBrID0gMDsgayA8IG51bUZlYXR1cmVzOyArK2spCgkJewoJCQljaW4gPj4gYWxsRmVhdHVyZXNbaV1ba107CgkJfQoJCWNpbiA+PiBhbGxBbnN3ZXJzW2ldOwoJfQoKCS8vIOOCt+ODo+ODg+ODleODq+eUqAoJdmVjdG9yIDwgaW50ID4gc2h1ZmZsZVRhYmxlOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBudW1UcmFpbmluZ3MrbnVtVGVzdHM7ICsraSkKCXsKCQlzaHVmZmxlVGFibGUuZW1wbGFjZV9iYWNrKGkpOwoJfQoJcmFuZG9tX3NodWZmbGUoc2h1ZmZsZVRhYmxlLmJlZ2luKCksIHNodWZmbGVUYWJsZS5lbmQoKSk7CgoJLy8g6KiT57e044OH44O844K/Cgl2ZWN0b3IgPCB2ZWN0b3IgPEZlYXR1cmVUeXBlPiA+IHRyYWluaW5nRmVhdHVyZXMobnVtVHJhaW5pbmdzLCB2ZWN0b3IgPEZlYXR1cmVUeXBlPihudW1GZWF0dXJlcykpOwoJdmVjdG9yIDwgQW5zd2VyVHlwZSA+CQl0cmFpbmluZ0Fuc3dlcnMobnVtVHJhaW5pbmdzKTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbnVtVHJhaW5pbmdzOyArK2kpCgl7CgkJdHJhaW5pbmdGZWF0dXJlc1tpXSA9IGFsbEZlYXR1cmVzW3NodWZmbGVUYWJsZVtpXV07CgkJdHJhaW5pbmdBbnN3ZXJzW2ldCT0gYWxsQW5zd2Vyc1tzaHVmZmxlVGFibGVbaV1dOwoJfQoKCS8vIOODhuOCueODiOODh+ODvOOCvwoJdmVjdG9yIDwgdmVjdG9yIDxGZWF0dXJlVHlwZT4gPiB0ZXN0RmVhdHVyZXMobnVtVGVzdHMsIHZlY3RvciA8RmVhdHVyZVR5cGU+KG51bUZlYXR1cmVzKSk7Cgl2ZWN0b3IgPCBBbnN3ZXJUeXBlID4JCXRlc3RBbnN3ZXJzKG51bVRlc3RzKTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbnVtVGVzdHM7ICsraSkKCXsKCQl0ZXN0RmVhdHVyZXNbaV0gPSBhbGxGZWF0dXJlc1tzaHVmZmxlVGFibGVbbnVtVHJhaW5pbmdzK2ldXTsKCQl0ZXN0QW5zd2Vyc1tpXQk9IGFsbEFuc3dlcnNbc2h1ZmZsZVRhYmxlW251bVRyYWluaW5ncytpXV07Cgl9CgoJLy8g44Op44Oz44OA44Og44OV44Kp44Os44K544OI44KS5L2/44Gj44Gm5LqI5risCglSYW5kb21Gb3Jlc3QqIHJmID0gbmV3IFJhbmRvbUZvcmVzdCgpOwoKCS8vIOWtpue/kgoJY29uc3QgaW50IG51bVRyZWVzID0gMTAwOwoJcmYtPnRyYWluKHRyYWluaW5nRmVhdHVyZXMsIHRyYWluaW5nQW5zd2VycywgNSwgOTk5LCAyLCA1LCAwLjY2ZiwgbnVtVHJlZXMpOwoKCS8vIOS6iOa4rOOBqOe1kOaenOihqOekugoJcHJpbnRmKCItLS0tLVxuIik7CgojaWYgSU5DTVNFCgl7CgkJdmVjdG9yIDxkb3VibGU+IHZkID0gcmYtPmNhbGN1bGF0ZUluY01TRSh0cmFpbmluZ0ZlYXR1cmVzLCB0cmFpbmluZ0Fuc3dlcnMsIDUpOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgU1oodmQpOyArK2kpCgkJewoJCQlwcmludGYoIkluY01TRSAgICAgICAgeCVkPSU4LjJmXG4iLGksdmRbaV0pOwoJCX0KCX0KI2VuZGlmIC8vIElOQ01TRQoKI2lmIElOQ05PREVQVVJJVFkKCXsKCQl2ZWN0b3IgPGRvdWJsZT4gdmQgPSByZi0+Y2FsY3VsYXRlSW5jTm9kZVB1cml0eSgpOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgU1oodmQpOyArK2kpCgkJewoJCQlwcmludGYoIkluY05vZGVQdXJpdHkgeCVkPSU4LjJmXG4iLGksdmRbaV0pOwoJCX0KCX0KI2VuZGlmIC8vIElOQ05PREVQVVJJVFkKCglkb3VibGUgdG90YWxFcnJvciA9IDAuMDsKCWZvciAoaW50IGkgPSAwOyBpIDwgbnVtVGVzdHM7ICsraSkKCXsKCQljb25zdCBkb3VibGUgbXlBbnN3ZXIgPSByZi0+ZXN0aW1hdGVSZWdyZXNzaW9uKHRlc3RGZWF0dXJlc1tpXSk7CgkJY29uc3QgZG91YmxlIGRpZmYgPSBteUFuc3dlci10ZXN0QW5zd2Vyc1tpXTsKCQl0b3RhbEVycm9yICs9IGFicyhkaWZmKTsKCQlwcmludGYoIlRlc3QlM2QgbXlBbnN3ZXI9JTguMmYgdGVzdEFuc3dlcj0lOC4yZiBkaWZmPSU4LjJmXG4iLCBpLCBteUFuc3dlciwgdGVzdEFuc3dlcnNbaV0sIGRpZmYpOwoJfQoJcHJpbnRmKCJ0b3RhbEVycm9yPSU4LjJmXG4iLHRvdGFsRXJyb3IpOwoJCgoJZGVsZXRlIHJmOwoKCXJldHVybiAwOwp9Cgo=

Success #stdin #stdout 0.01s 3296KB

stdin

copy

44 30 14 6
6.9	1.8	30.2	58.3	27.3	84.9	-14.2
8.4	28.5	38.8	87.5	39.8	172.6	-34.1
5.7	7.8	31.7	83.5	26	154.2	-15.8
7.4	2.3	24.2	14.2	29.4	35.2	-13.9
8.5	-0.7	28.1	46.7	26.6	69.2	-13.9
13.8	7.2	10.4	57.9	26.2	111	-22.6
1.7	32.2	7.5	73.8	50.5	704.1	-40.9
3.6	7.4	30	61.3	26.4	69.9	4
8.2	10.2	12.1	41	11.7	65.4	-32.5
5	10.5	13.6	17.4	14.7	132.1	-8.1
2.1	0.3	18.3	34.4	24.2	179.9	12.3
4.2	8.1	21.3	64.9	21.7	139.9	-35
3.9	2	33.1	82	26.3	108.7	-2
4.1	10.8	38.3	83.3	32.6	123.2	-2.2
4.2	1.9	36.9	61.8	21.6	104.7	-14.2
9.4	-1.5	22.4	22.2	33.5	61.5	-32.7
3.6	-0.3	19.6	8.6	27	68.2	-13.4
7.6	5.5	29.1	62.8	32.2	96.9	-8.7
8.5	4.8	32.8	86.2	16	258	0.5
7.5	2.3	26.5	18.7	23.7	32	-0.6
4.1	17.3	41.5	78.6	23.5	127	-12.5
4.6	68.6	39	14.6	38.2	27.1	45.4
7.2	3	20.2	41.4	27.6	70.7	-38.2
13.4	7.1	20.4	13.9	22.5	38.3	-33.6
10.3	1.4	29.8	43.7	29.4	54	-10
9.4	4.6	36	78.2	29.9	101.5	-14.6
2.5	-3.3	37.6	88.5	27.5	185.9	-7.6
10.3	-0.5	31.8	57.2	27.2	61.2	-17.6
7.5	22.3	28.6	5.7	31.3	38.6	27.2
18.7	6.2	39.7	55.8	28.7	52.6	-2.9
5.1	-2	23.8	29	29.3	62.6	-10.3
3.7	19.6	12.3	77.3	32	207.7	-45.6
10.3	3	31.1	51.7	26.2	42.4	-31.9
7.3	19.2	32.9	68.1	25.2	105.2	-35.7
4.2	7	22.1	41.2	21.4	68.6	-8.8
2.1	5.4	27.1	60	23.5	157.3	6.2
2.5	2.8	20.3	29.8	24.1	58.5	-27.5
8.1	8.5	30	66.4	26	63.1	-37.4
10.3	-1.9	15.9	39.9	38.5	86.4	-13.5
10.5	2.8	36.4	72.3	26	77.5	-21.6
5.8	2	24.2	19.5	28.3	63.5	2.2
6.9	2.9	20.7	6.6	25.8	68.9	-2.4
9.3	4.9	34.9	82.4	18.4	102.8	-12
11.4	2.6	38.7	78.2	18.4	86.6	-12.8

stdout

copy

-----
IncMSE        x0=   -6.46
IncMSE        x1=    5.80
IncMSE        x2=  -12.16
IncMSE        x3=   66.87
IncMSE        x4=  -15.22
IncMSE        x5=    0.69
IncNodePurity x0=  599.36
IncNodePurity x1=  958.41
IncNodePurity x2=  890.15
IncNodePurity x3= 1276.43
IncNodePurity x4=  805.89
IncNodePurity x5= 1258.49
Test  0 myAnswer=  -11.36 testAnswer=  -10.30 diff=   -1.06
Test  1 myAnswer=  -15.27 testAnswer=  -13.50 diff=   -1.77
Test  2 myAnswer=  -14.47 testAnswer=   -2.20 diff=  -12.27
Test  3 myAnswer=  -15.27 testAnswer=  -37.40 diff=   22.13
Test  4 myAnswer=    0.57 testAnswer=  -13.90 diff=   14.47
Test  5 myAnswer=   -5.69 testAnswer=  -13.40 diff=    7.71
Test  6 myAnswer=   -6.41 testAnswer=   -2.90 diff=   -3.51
Test  7 myAnswer=  -14.62 testAnswer=  -12.80 diff=   -1.82
Test  8 myAnswer=   -8.04 testAnswer=   -8.10 diff=    0.06
Test  9 myAnswer=  -11.27 testAnswer=  -38.20 diff=   26.93
Test 10 myAnswer=  -14.22 testAnswer=  -32.50 diff=   18.28
Test 11 myAnswer=   -4.54 testAnswer=  -33.60 diff=   29.06
Test 12 myAnswer=   -9.10 testAnswer=  -12.50 diff=    3.40
Test 13 myAnswer=  -11.43 testAnswer=   -8.80 diff=   -2.63
totalError=  145.10

https://ideone.com/RYF0Bn

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language