#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <tuple>
#include <string>
using namespace std;
using Portfolio = vector<int>; // weights in percent, size = 6
double percentile15(vector<double>& data) {
sort(data.begin(), data.end());
size_t index = static_cast<size_t>(floor(0.15 * data.size()));
if (index >= data.size()) index = data.size() - 1;
return data[index];
}
double median(vector<double>& data) {
sort(data.begin(), data.end());
size_t n = data.size();
if (n % 2 == 0)
return (data[n / 2 - 1] + data[n / 2]) / 2.0;
else
return data[n / 2];
}
double lumpSumCAGR(const vector<double>& returns) {
double compound = 1.0;
for (double r : returns) {
compound *= (1.0 + r);
}
return pow(compound, 1.0 / returns.size()) - 1.0;
}
double portfolioReturn(const vector<vector<double>>& assets, const Portfolio& weights, int year) {
double result = 0.0;
for (int i = 0; i < weights.size(); ++i) {
result += (weights[i] / 100.0) * assets[i][year];
}
return result;
}
void generatePortfolios(vector<Portfolio>& portfolios, Portfolio current, int pos, int totalWeight, int maxAssets) {
if (pos == current.size()) {
if (totalWeight == 100) {
int nonZero = count_if(current.begin(), current.end(), [](int w) { return w > 0; });
if (nonZero <= maxAssets) {
portfolios.push_back(current);
}
}
return;
}
for (int w = 0; w <= 100 - totalWeight; w += 20) {//const int step = 10;
current[pos] = w;
generatePortfolios(portfolios, current, pos + 1, totalWeight + w, maxAssets);
}
}
int main() {
const int numAssets = 8;
const int maxAssets = 5;
// Asset names
vector<string> assetNames = {
"scv", "lcg", "em", "reit", "gld" , "eu ltb", "vti","20bal", "33gld"
//"scv60Lcg15", "scv95", "vti", "20bal", "33gld", "lcbtiltled"
};
// Return data
vector<vector<double>> assets = {
{-0.03,0.13,0.06,-0.29,-0.31,0.43,0.46,0.08,0.07,0.21,0.12,0.06,0.31,0.38,0.02,0.31,0.12,-0.08,0.23,0.14,-0.22,0.37,0.24,0.19,-0.02,0.24,0.17,0.31,-0.06,0.02,0.04,0.11,-0.13,0.41,0.17,0.04,0.15,-0.09,-0.32,0.33,0.23,-0.06,0.18,0.32,0.09,-0.06,0.23,0.09,-0.15,0.20,0.03,0.19,-0.16,0.11,0.08},
{
-0.09, 0.19, 0.18, -0.28, -0.40, 0.24, 0.08, -0.16, -0.02, 0.01,
0.16, -0.16, 0.20, 0.14, -0.01, 0.30, 0.14, 0.01, 0.07, 0.32,
-0.05, 0.37, 0.03, 0.00, 0.01, 0.34, 0.22, 0.32, 0.43, 0.29,
-0.28, -0.13, -0.24, 0.23, 0.04, 0.02, 0.07, 0.06, -0.39, 0.33,
0.15, -0.01, 0.15, 0.31, 0.13, 0.03, 0.05, 0.25, -0.04, 0.34,
0.39, 0.18, -0.35, 0.40, 0.31
},
{
-0.17, 0.28, 0.34, -0.18, -0.28, 0.25, 0.04, 0.01, 0.05, 0.06,
-0.04, -0.25, -0.31, 0.12, 0.12, 0.23, 0.11, 0.09, 0.34, 0.55,
-0.16, 0.54, 0.09, 0.68, -0.09, -0.06, 0.03, -0.11, -0.25, 0.59,
-0.31, -0.03, -0.08, 0.53, 0.22, 0.29, 0.29, 0.32, -0.52, 0.72,
0.18, -0.20, 0.17, -0.02, -0.02, -0.15, 0.10, 0.34, -0.16, 0.16,
0.16, -0.07, -0.24, 0.09, 0.05
},
{
-0.01, 0.10, 0.05, -0.23, -0.30, 0.13, 0.41, 0.14, 0.01, 0.20,
0.11, -0.02, 0.18, 0.26, 0.16, 0.16, 0.18, -0.08, 0.09, 0.04,
-0.20, 0.32, 0.12, 0.17, 0.00, 0.13, 0.30, 0.19, -0.18, -0.07,
0.21, 0.12, 0.01, 0.35, 0.27, 0.08, 0.31, -0.19, -0.37, 0.25,
0.26, 0.05, 0.16, 0.03, 0.28, 0.02, 0.07, 0.03, -0.07, 0.23,
-0.09, 0.33, -0.28, 0.10, 0.06
},
{
0.00, 0.13, 0.42, 0.55, 0.44, -0.26, -0.06, 0.15, 0.25, 1.00,
0.01, -0.36, 0.13, -0.17, -0.21, 0.04, 0.17, 0.18, -0.17, -0.06,
-0.09, -0.09, -0.07, 0.15, -0.05, 0.00, -0.06, -0.20, -0.03, -0.02,
-0.08, 0.00, 0.21, 0.19, 0.02, 0.13, 0.20, 0.25, 0.02, 0.22,
0.27, 0.05, 0.07, -0.25, 0.00, -0.12, 0.07, 0.10, -0.03, 0.16,
0.22, -0.09, -0.06, 0.11, 0.21
},
{
-0.02, 0.16, 0.04, -0.04, -0.10, 0.08, -0.05, 0.16, 0.15, -0.10,
-0.16, -0.16, -0.23, 0.09, -0.02, 0.04, 0.43, 0.48, 0.17, -0.02,
-0.02, 0.12, 0.14, -0.02, 0.24, -0.03, 0.24, 0.18, 0.02, 0.22,
-0.24, 0.01, 0.00, 0.28, 0.24, 0.19, -0.04, 0.06, 0.03, 0.04,
0.05, -0.03, -0.01, 0.17, 0.05, 0.14, -0.08, 0.02, 0.10, -0.04,
0.11, 0.20, -0.18, -0.41, 0.11, -0.08
},
// {-0.04,0.14,0.15,-0.14,-0.19,0.26,0.28,0.04,0.08,0.28,0.08,-0.06,0.24,0.22,-0.01,0.26,0.14,-0.02,0.14,0.16,-0.16,0.29,0.15,0.18,-0.03,0.20,0.13,0.20,0.02,0.08,-0.04,0.04,-0.07,0.33,0.12,0.06,0.15,0.01,-0.26,0.31,0.22,-0.03,0.15,0.19,0.08,-0.06,0.16,0.13,-0.11,0.21,0.13,0.12,-0.18,0.15,0.12},
// {-0.03,0.13,0.06,-0.29,-0.31,0.43,0.46,0.08,0.07,0.21,0.12,0.06,0.31,0.38,0.02,0.31,0.12,-0.08,0.23,0.14,-0.22,0.37,0.24,0.19,-0.02,0.24,0.17,0.31,-0.06,0.02,0.04,0.11,-0.13,0.41,0.17,0.04,0.15,-0.09,-0.32,0.33,0.23,-0.06,0.18,0.32,0.09,-0.06,0.23,0.09,-0.15,0.20,0.03,0.19,-0.16,0.11,0.08},
{-0.02,0.11,0.12,-0.25,-0.36,0.30,0.21,-0.11,-0.01,0.05,0.16,-0.11,0.19,0.19,0.01,0.28,0.15,-0.02,0.12,0.24,-0.10,0.29,0.06,0.08,-0.01,0.34,0.19,0.30,0.24,0.19,-0.13,-0.09,-0.25,0.30,0.08,0.02,0.12,0.01,-0.37,0.26,0.16,-0.02,0.14,0.31,0.12,0.00,0.11,0.19,-0.07,0.28,0.19,0.18,-0.24,0.22,0.20},
{-0.03,0.15,0.18,-0.07,-0.14,0.12,0.18,0.04,0.07,0.28,0.06,-0.13,0.17,0.13,0.01,0.22,0.18,0.02,0.07,0.14,-0.13,0.23,0.06,0.17,-0.02,0.16,0.12,0.12,0.04,0.07,-0.03,0.01,-0.02,0.29,0.13,0.08,0.17,0.03,-0.23,0.27,0.21,0.02,0.13,0.07,0.12,-0.03,0.09,0.13,-0.08,0.22,0.14,0.11,-0.23,0.16,0.13},
{-0.01,0.11,0.19,0.03,-0.05,0.13,0.23,0.07,0.10,0.44,0.08,-0.13,0.20,0.14,-0.04,0.19,0.16,0.02,0.06,0.08,-0.15,0.17,0.08,0.16,-0.03,0.17,0.11,0.12,0.00,0.02,-0.01,0.02,-0.02,0.30,0.11,0.07,0.19,0.03,-0.21,0.25,0.23,0.00,0.13,0.08,0.09,-0.06,0.13,0.10,-0.08,0.20,0.10,0.11,-0.14,0.11,0.14},
// {-0.03,0.13,0.12,-0.22,-0.30,0.25,0.24,-0.02,0.00,0.07,0.08,-0.09,0.14,0.20,0.07,0.26,0.15,-0.02,0.16,0.24,-0.13,0.33,0.10,0.21,-0.03,0.22,0.16,0.21,0.05,0.15,-0.05,-0.02,-0.12,0.32,0.14,0.08,0.17,0.02,-0.32,0.29,0.17,-0.01,0.14,0.17,0.13,-0.03,0.11,0.16,-0.09,0.23,0.11,0.14,-0.24,0.14,0.11}
//
};
int numYears = assets[0].size();
for (int duration = 1; duration <= 31; duration += 1) {
cout << "\n========== Duration: " << duration << " years ==========" << endl;
vector<Portfolio> portfolios;
generatePortfolios(portfolios, Portfolio(numAssets, 0), 0, 0, maxAssets);
vector<tuple<Portfolio, double, double, double, double>> results;
for (const Portfolio& p : portfolios) {
vector<double> cagrList;
for (int start = 0; start <= numYears - duration; ++start) {
vector<double> subReturns;
for (int i = 0; i < duration; ++i) {
subReturns.push_back(portfolioReturn(assets, p, start + i));
}
double cagr = lumpSumCAGR(subReturns);
cagrList.push_back(cagr);
}
double p15 = percentile15(cagrList);
double pmin = *min_element(cagrList.begin(), cagrList.end());
double pmax = *max_element(cagrList.begin(), cagrList.end());
double pmed = median(cagrList);
results.emplace_back(p, p15, pmin, pmax, pmed);
}
sort(results.begin(), results.end(), [](const auto& a, const auto& b) {
return get<1>(a) > get<1>(b);
});
cout << fixed << setprecision(2);
// Summary table
cout << "\nTop 2 Portfolios Summary (Bottom 15th Percentile CAGR):" << endl;
cout << left << setw(10) << "#" << setw(40) << "Portfolio" << setw(10) << "P15%" << setw(10) << "Min" << setw(10) << "Max" << setw(10) << "Median" << endl;
cout << string(80, '-') << endl;
for (int i = 0; i < 2 && i < results.size(); ++i) {
auto [weights, p15, pmin, pmax, pmed] = results[i];
string portStr;
for (int j = 0; j < numAssets; ++j) {
if (weights[j] > 0) {
portStr += assetNames[j] + ":" + to_string(weights[j]) + "% ";
}
}
cout << left << setw(10) << (i + 1) << setw(40) << portStr << setw(10) << p15 * 100 << setw(10) << pmin * 100 << setw(10) << pmax * 100 << setw(10) << pmed * 100 << endl;
}
// // Detailed breakdown
// for (int i = 0; i < 2 && i < results.size(); ++i) {
// auto [weights, p15, pmin, pmax, pmed] = results[i];
// cout << "\nPortfolio " << (i + 1) << ":\n";
// cout << left << setw(15) << "Asset" << setw(10) << "Weight\n";
// cout << "-------------------------\n";
// for (int j = 0; j < numAssets; ++j) {
// if (weights[j] > 0) {
// cout << left << setw(15) << assetNames[j] << setw(10) << weights[j] << "\n";
// }
// }
// cout << "-------------------------\n";
// cout << "Bottom 15th % CAGR : " << p15 * 100 << "%\n";
// cout << "Min CAGR : " << pmin * 100 << "%\n";
// cout << "Max CAGR : " << pmax * 100 << "%\n";
// cout << "Median CAGR : " << pmed * 100 << "%\n";
// }
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxpb21hbmlwPgojaW5jbHVkZSA8dHVwbGU+CiNpbmNsdWRlIDxzdHJpbmc+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdXNpbmcgUG9ydGZvbGlvID0gdmVjdG9yPGludD47IC8vIHdlaWdodHMgaW4gcGVyY2VudCwgc2l6ZSA9IDYKCmRvdWJsZSBwZXJjZW50aWxlMTUodmVjdG9yPGRvdWJsZT4mIGRhdGEpIHsKICAgIHNvcnQoZGF0YS5iZWdpbigpLCBkYXRhLmVuZCgpKTsKICAgIHNpemVfdCBpbmRleCA9IHN0YXRpY19jYXN0PHNpemVfdD4oZmxvb3IoMC4xNSAqIGRhdGEuc2l6ZSgpKSk7CiAgICBpZiAoaW5kZXggPj0gZGF0YS5zaXplKCkpIGluZGV4ID0gZGF0YS5zaXplKCkgLSAxOwogICAgcmV0dXJuIGRhdGFbaW5kZXhdOwp9Cgpkb3VibGUgbWVkaWFuKHZlY3Rvcjxkb3VibGU+JiBkYXRhKSB7CiAgICBzb3J0KGRhdGEuYmVnaW4oKSwgZGF0YS5lbmQoKSk7CiAgICBzaXplX3QgbiA9IGRhdGEuc2l6ZSgpOwogICAgaWYgKG4gJSAyID09IDApCiAgICAgICAgcmV0dXJuIChkYXRhW24gLyAyIC0gMV0gKyBkYXRhW24gLyAyXSkgLyAyLjA7CiAgICBlbHNlCiAgICAgICAgcmV0dXJuIGRhdGFbbiAvIDJdOwp9Cgpkb3VibGUgbHVtcFN1bUNBR1IoY29uc3QgdmVjdG9yPGRvdWJsZT4mIHJldHVybnMpIHsKICAgIGRvdWJsZSBjb21wb3VuZCA9IDEuMDsKICAgIGZvciAoZG91YmxlIHIgOiByZXR1cm5zKSB7CiAgICAgICAgY29tcG91bmQgKj0gKDEuMCArIHIpOwogICAgfQogICAgcmV0dXJuIHBvdyhjb21wb3VuZCwgMS4wIC8gcmV0dXJucy5zaXplKCkpIC0gMS4wOwp9Cgpkb3VibGUgcG9ydGZvbGlvUmV0dXJuKGNvbnN0IHZlY3Rvcjx2ZWN0b3I8ZG91YmxlPj4mIGFzc2V0cywgY29uc3QgUG9ydGZvbGlvJiB3ZWlnaHRzLCBpbnQgeWVhcikgewogICAgZG91YmxlIHJlc3VsdCA9IDAuMDsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgd2VpZ2h0cy5zaXplKCk7ICsraSkgewogICAgICAgIHJlc3VsdCArPSAod2VpZ2h0c1tpXSAvIDEwMC4wKSAqIGFzc2V0c1tpXVt5ZWFyXTsKICAgIH0KICAgIHJldHVybiByZXN1bHQ7Cn0KCnZvaWQgZ2VuZXJhdGVQb3J0Zm9saW9zKHZlY3RvcjxQb3J0Zm9saW8+JiBwb3J0Zm9saW9zLCBQb3J0Zm9saW8gY3VycmVudCwgaW50IHBvcywgaW50IHRvdGFsV2VpZ2h0LCBpbnQgbWF4QXNzZXRzKSB7CiAgICBpZiAocG9zID09IGN1cnJlbnQuc2l6ZSgpKSB7CiAgICAgICAgaWYgKHRvdGFsV2VpZ2h0ID09IDEwMCkgewogICAgICAgICAgICBpbnQgbm9uWmVybyA9IGNvdW50X2lmKGN1cnJlbnQuYmVnaW4oKSwgY3VycmVudC5lbmQoKSwgW10oaW50IHcpIHsgcmV0dXJuIHcgPiAwOyB9KTsKICAgICAgICAgICAgaWYgKG5vblplcm8gPD0gbWF4QXNzZXRzKSB7CiAgICAgICAgICAgICAgICBwb3J0Zm9saW9zLnB1c2hfYmFjayhjdXJyZW50KTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICByZXR1cm47CiAgICB9CiAgICBmb3IgKGludCB3ID0gMDsgdyA8PSAxMDAgLSB0b3RhbFdlaWdodDsgdyArPSAyMCkgey8vY29uc3QgaW50IHN0ZXAgPSAxMDsKICAgICAgICBjdXJyZW50W3Bvc10gPSB3OwogICAgICAgIGdlbmVyYXRlUG9ydGZvbGlvcyhwb3J0Zm9saW9zLCBjdXJyZW50LCBwb3MgKyAxLCB0b3RhbFdlaWdodCArIHcsIG1heEFzc2V0cyk7CiAgICB9Cn0KCmludCBtYWluKCkgewogICAgY29uc3QgaW50IG51bUFzc2V0cyA9IDg7CiAgICBjb25zdCBpbnQgbWF4QXNzZXRzID0gNTsKICAgIAoKICAgIC8vIEFzc2V0IG5hbWVzCiAgICB2ZWN0b3I8c3RyaW5nPiBhc3NldE5hbWVzID0gewogICAgCSJzY3YiLCAibGNnIiwgImVtIiwgInJlaXQiLCAiZ2xkIiAsICJldSBsdGIiLCAidnRpIiwiMjBiYWwiLCAiMzNnbGQiCiAgICAgICAgLy8ic2N2NjBMY2cxNSIsICJzY3Y5NSIsICJ2dGkiLCAiMjBiYWwiLCAiMzNnbGQiLCAibGNidGlsdGxlZCIKICAgIH07CgogICAgLy8gUmV0dXJuIGRhdGEKICAgIHZlY3Rvcjx2ZWN0b3I8ZG91YmxlPj4gYXNzZXRzID0gewogICAgCQogICAgCSAgICAgICAgIHstMC4wMywwLjEzLDAuMDYsLTAuMjksLTAuMzEsMC40MywwLjQ2LDAuMDgsMC4wNywwLjIxLDAuMTIsMC4wNiwwLjMxLDAuMzgsMC4wMiwwLjMxLDAuMTIsLTAuMDgsMC4yMywwLjE0LC0wLjIyLDAuMzcsMC4yNCwwLjE5LC0wLjAyLDAuMjQsMC4xNywwLjMxLC0wLjA2LDAuMDIsMC4wNCwwLjExLC0wLjEzLDAuNDEsMC4xNywwLjA0LDAuMTUsLTAuMDksLTAuMzIsMC4zMywwLjIzLC0wLjA2LDAuMTgsMC4zMiwwLjA5LC0wLjA2LDAuMjMsMC4wOSwtMC4xNSwwLjIwLDAuMDMsMC4xOSwtMC4xNiwwLjExLDAuMDh9LAoKICAgIAkKICAgIAl7CiAgICAtMC4wOSwgMC4xOSwgMC4xOCwgLTAuMjgsIC0wLjQwLCAwLjI0LCAwLjA4LCAtMC4xNiwgLTAuMDIsIDAuMDEsCiAgICAwLjE2LCAtMC4xNiwgMC4yMCwgMC4xNCwgLTAuMDEsIDAuMzAsIDAuMTQsIDAuMDEsIDAuMDcsIDAuMzIsCiAgICAtMC4wNSwgMC4zNywgMC4wMywgMC4wMCwgMC4wMSwgMC4zNCwgMC4yMiwgMC4zMiwgMC40MywgMC4yOSwKICAgIC0wLjI4LCAtMC4xMywgLTAuMjQsIDAuMjMsIDAuMDQsIDAuMDIsIDAuMDcsIDAuMDYsIC0wLjM5LCAwLjMzLAogICAgMC4xNSwgLTAuMDEsIDAuMTUsIDAuMzEsIDAuMTMsIDAuMDMsIDAuMDUsIDAuMjUsIC0wLjA0LCAwLjM0LAogICAgMC4zOSwgMC4xOCwgLTAuMzUsIDAuNDAsIDAuMzEKfSwKCnsKICAgIC0wLjE3LCAwLjI4LCAwLjM0LCAtMC4xOCwgLTAuMjgsIDAuMjUsIDAuMDQsIDAuMDEsIDAuMDUsIDAuMDYsCiAgICAtMC4wNCwgLTAuMjUsIC0wLjMxLCAwLjEyLCAwLjEyLCAwLjIzLCAwLjExLCAwLjA5LCAwLjM0LCAwLjU1LAogICAgLTAuMTYsIDAuNTQsIDAuMDksIDAuNjgsIC0wLjA5LCAtMC4wNiwgMC4wMywgLTAuMTEsIC0wLjI1LCAwLjU5LAogICAgLTAuMzEsIC0wLjAzLCAtMC4wOCwgMC41MywgMC4yMiwgMC4yOSwgMC4yOSwgMC4zMiwgLTAuNTIsIDAuNzIsCiAgICAwLjE4LCAtMC4yMCwgMC4xNywgLTAuMDIsIC0wLjAyLCAtMC4xNSwgMC4xMCwgMC4zNCwgLTAuMTYsIDAuMTYsCiAgICAwLjE2LCAtMC4wNywgLTAuMjQsIDAuMDksIDAuMDUKfSwKCnsKICAgIC0wLjAxLCAwLjEwLCAwLjA1LCAtMC4yMywgLTAuMzAsIDAuMTMsIDAuNDEsIDAuMTQsIDAuMDEsIDAuMjAsCiAgICAwLjExLCAtMC4wMiwgMC4xOCwgMC4yNiwgMC4xNiwgMC4xNiwgMC4xOCwgLTAuMDgsIDAuMDksIDAuMDQsCiAgICAtMC4yMCwgMC4zMiwgMC4xMiwgMC4xNywgMC4wMCwgMC4xMywgMC4zMCwgMC4xOSwgLTAuMTgsIC0wLjA3LAogICAgMC4yMSwgMC4xMiwgMC4wMSwgMC4zNSwgMC4yNywgMC4wOCwgMC4zMSwgLTAuMTksIC0wLjM3LCAwLjI1LAogICAgMC4yNiwgMC4wNSwgMC4xNiwgMC4wMywgMC4yOCwgMC4wMiwgMC4wNywgMC4wMywgLTAuMDcsIDAuMjMsCiAgICAtMC4wOSwgMC4zMywgLTAuMjgsIDAuMTAsIDAuMDYKfSwKCnsKMC4wMCwgMC4xMywgMC40MiwgMC41NSwgMC40NCwgLTAuMjYsIC0wLjA2LCAwLjE1LCAwLjI1LCAxLjAwLAowLjAxLCAtMC4zNiwgMC4xMywgLTAuMTcsIC0wLjIxLCAwLjA0LCAwLjE3LCAwLjE4LCAtMC4xNywgLTAuMDYsCi0wLjA5LCAtMC4wOSwgLTAuMDcsIDAuMTUsIC0wLjA1LCAwLjAwLCAtMC4wNiwgLTAuMjAsIC0wLjAzLCAtMC4wMiwKLTAuMDgsIDAuMDAsIDAuMjEsIDAuMTksIDAuMDIsIDAuMTMsIDAuMjAsIDAuMjUsIDAuMDIsIDAuMjIsCjAuMjcsIDAuMDUsIDAuMDcsIC0wLjI1LCAwLjAwLCAtMC4xMiwgMC4wNywgMC4xMCwgLTAuMDMsIDAuMTYsCjAuMjIsIC0wLjA5LCAtMC4wNiwgMC4xMSwgMC4yMQp9LAoKewogICAgLTAuMDIsIDAuMTYsIDAuMDQsIC0wLjA0LCAtMC4xMCwgMC4wOCwgLTAuMDUsIDAuMTYsIDAuMTUsIC0wLjEwLAogICAgLTAuMTYsIC0wLjE2LCAtMC4yMywgMC4wOSwgLTAuMDIsIDAuMDQsIDAuNDMsIDAuNDgsIDAuMTcsIC0wLjAyLAogICAgLTAuMDIsIDAuMTIsIDAuMTQsIC0wLjAyLCAwLjI0LCAtMC4wMywgMC4yNCwgMC4xOCwgMC4wMiwgMC4yMiwKICAgIC0wLjI0LCAwLjAxLCAwLjAwLCAwLjI4LCAwLjI0LCAwLjE5LCAtMC4wNCwgMC4wNiwgMC4wMywgMC4wNCwKICAgIDAuMDUsIC0wLjAzLCAtMC4wMSwgMC4xNywgMC4wNSwgMC4xNCwgLTAuMDgsIDAuMDIsIDAuMTAsIC0wLjA0LAogICAgMC4xMSwgMC4yMCwgLTAuMTgsIC0wLjQxLCAwLjExLCAtMC4wOAp9LAoKICAgIAkKLy8gICAgICAgICB7LTAuMDQsMC4xNCwwLjE1LC0wLjE0LC0wLjE5LDAuMjYsMC4yOCwwLjA0LDAuMDgsMC4yOCwwLjA4LC0wLjA2LDAuMjQsMC4yMiwtMC4wMSwwLjI2LDAuMTQsLTAuMDIsMC4xNCwwLjE2LC0wLjE2LDAuMjksMC4xNSwwLjE4LC0wLjAzLDAuMjAsMC4xMywwLjIwLDAuMDIsMC4wOCwtMC4wNCwwLjA0LC0wLjA3LDAuMzMsMC4xMiwwLjA2LDAuMTUsMC4wMSwtMC4yNiwwLjMxLDAuMjIsLTAuMDMsMC4xNSwwLjE5LDAuMDgsLTAuMDYsMC4xNiwwLjEzLC0wLjExLDAuMjEsMC4xMywwLjEyLC0wLjE4LDAuMTUsMC4xMn0sCi8vICAgICAgICAgey0wLjAzLDAuMTMsMC4wNiwtMC4yOSwtMC4zMSwwLjQzLDAuNDYsMC4wOCwwLjA3LDAuMjEsMC4xMiwwLjA2LDAuMzEsMC4zOCwwLjAyLDAuMzEsMC4xMiwtMC4wOCwwLjIzLDAuMTQsLTAuMjIsMC4zNywwLjI0LDAuMTksLTAuMDIsMC4yNCwwLjE3LDAuMzEsLTAuMDYsMC4wMiwwLjA0LDAuMTEsLTAuMTMsMC40MSwwLjE3LDAuMDQsMC4xNSwtMC4wOSwtMC4zMiwwLjMzLDAuMjMsLTAuMDYsMC4xOCwwLjMyLDAuMDksLTAuMDYsMC4yMywwLjA5LC0wLjE1LDAuMjAsMC4wMywwLjE5LC0wLjE2LDAuMTEsMC4wOH0sCiAgICAgICAgIHstMC4wMiwwLjExLDAuMTIsLTAuMjUsLTAuMzYsMC4zMCwwLjIxLC0wLjExLC0wLjAxLDAuMDUsMC4xNiwtMC4xMSwwLjE5LDAuMTksMC4wMSwwLjI4LDAuMTUsLTAuMDIsMC4xMiwwLjI0LC0wLjEwLDAuMjksMC4wNiwwLjA4LC0wLjAxLDAuMzQsMC4xOSwwLjMwLDAuMjQsMC4xOSwtMC4xMywtMC4wOSwtMC4yNSwwLjMwLDAuMDgsMC4wMiwwLjEyLDAuMDEsLTAuMzcsMC4yNiwwLjE2LC0wLjAyLDAuMTQsMC4zMSwwLjEyLDAuMDAsMC4xMSwwLjE5LC0wLjA3LDAuMjgsMC4xOSwwLjE4LC0wLjI0LDAuMjIsMC4yMH0sCnstMC4wMywwLjE1LDAuMTgsLTAuMDcsLTAuMTQsMC4xMiwwLjE4LDAuMDQsMC4wNywwLjI4LDAuMDYsLTAuMTMsMC4xNywwLjEzLDAuMDEsMC4yMiwwLjE4LDAuMDIsMC4wNywwLjE0LC0wLjEzLDAuMjMsMC4wNiwwLjE3LC0wLjAyLDAuMTYsMC4xMiwwLjEyLDAuMDQsMC4wNywtMC4wMywwLjAxLC0wLjAyLDAuMjksMC4xMywwLjA4LDAuMTcsMC4wMywtMC4yMywwLjI3LDAuMjEsMC4wMiwwLjEzLDAuMDcsMC4xMiwtMC4wMywwLjA5LDAuMTMsLTAuMDgsMC4yMiwwLjE0LDAuMTEsLTAuMjMsMC4xNiwwLjEzfSwgICAgICAgIAp7LTAuMDEsMC4xMSwwLjE5LDAuMDMsLTAuMDUsMC4xMywwLjIzLDAuMDcsMC4xMCwwLjQ0LDAuMDgsLTAuMTMsMC4yMCwwLjE0LC0wLjA0LDAuMTksMC4xNiwwLjAyLDAuMDYsMC4wOCwtMC4xNSwwLjE3LDAuMDgsMC4xNiwtMC4wMywwLjE3LDAuMTEsMC4xMiwwLjAwLDAuMDIsLTAuMDEsMC4wMiwtMC4wMiwwLjMwLDAuMTEsMC4wNywwLjE5LDAuMDMsLTAuMjEsMC4yNSwwLjIzLDAuMDAsMC4xMywwLjA4LDAuMDksLTAuMDYsMC4xMywwLjEwLC0wLjA4LDAuMjAsMC4xMCwwLjExLC0wLjE0LDAuMTEsMC4xNH0sCi8vICAgICAgICAgey0wLjAzLDAuMTMsMC4xMiwtMC4yMiwtMC4zMCwwLjI1LDAuMjQsLTAuMDIsMC4wMCwwLjA3LDAuMDgsLTAuMDksMC4xNCwwLjIwLDAuMDcsMC4yNiwwLjE1LC0wLjAyLDAuMTYsMC4yNCwtMC4xMywwLjMzLDAuMTAsMC4yMSwtMC4wMywwLjIyLDAuMTYsMC4yMSwwLjA1LDAuMTUsLTAuMDUsLTAuMDIsLTAuMTIsMC4zMiwwLjE0LDAuMDgsMC4xNywwLjAyLC0wLjMyLDAuMjksMC4xNywtMC4wMSwwLjE0LDAuMTcsMC4xMywtMC4wMywwLjExLDAuMTYsLTAuMDksMC4yMywwLjExLDAuMTQsLTAuMjQsMC4xNCwwLjExfQovLyAgICAgCgogICAgCQogICAgfTsKCiAgICBpbnQgbnVtWWVhcnMgPSBhc3NldHNbMF0uc2l6ZSgpOwoKICAgIGZvciAoaW50IGR1cmF0aW9uID0gMTsgZHVyYXRpb24gPD0gMzE7IGR1cmF0aW9uICs9IDEpIHsKICAgICAgICBjb3V0IDw8ICJcbj09PT09PT09PT0gRHVyYXRpb246ICIgPDwgZHVyYXRpb24gPDwgIiB5ZWFycyA9PT09PT09PT09IiA8PCBlbmRsOwoKICAgICAgICB2ZWN0b3I8UG9ydGZvbGlvPiBwb3J0Zm9saW9zOwogICAgICAgIGdlbmVyYXRlUG9ydGZvbGlvcyhwb3J0Zm9saW9zLCBQb3J0Zm9saW8obnVtQXNzZXRzLCAwKSwgMCwgMCwgbWF4QXNzZXRzKTsKCiAgICAgICAgdmVjdG9yPHR1cGxlPFBvcnRmb2xpbywgZG91YmxlLCBkb3VibGUsIGRvdWJsZSwgZG91YmxlPj4gcmVzdWx0czsKCiAgICAgICAgZm9yIChjb25zdCBQb3J0Zm9saW8mIHAgOiBwb3J0Zm9saW9zKSB7CiAgICAgICAgICAgIHZlY3Rvcjxkb3VibGU+IGNhZ3JMaXN0OwogICAgICAgICAgICBmb3IgKGludCBzdGFydCA9IDA7IHN0YXJ0IDw9IG51bVllYXJzIC0gZHVyYXRpb247ICsrc3RhcnQpIHsKICAgICAgICAgICAgICAgIHZlY3Rvcjxkb3VibGU+IHN1YlJldHVybnM7CiAgICAgICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGR1cmF0aW9uOyArK2kpIHsKICAgICAgICAgICAgICAgICAgICBzdWJSZXR1cm5zLnB1c2hfYmFjayhwb3J0Zm9saW9SZXR1cm4oYXNzZXRzLCBwLCBzdGFydCArIGkpKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGRvdWJsZSBjYWdyID0gbHVtcFN1bUNBR1Ioc3ViUmV0dXJucyk7CiAgICAgICAgICAgICAgICBjYWdyTGlzdC5wdXNoX2JhY2soY2Fncik7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGRvdWJsZSBwMTUgPSBwZXJjZW50aWxlMTUoY2Fnckxpc3QpOwogICAgICAgICAgICBkb3VibGUgcG1pbiA9ICptaW5fZWxlbWVudChjYWdyTGlzdC5iZWdpbigpLCBjYWdyTGlzdC5lbmQoKSk7CiAgICAgICAgICAgIGRvdWJsZSBwbWF4ID0gKm1heF9lbGVtZW50KGNhZ3JMaXN0LmJlZ2luKCksIGNhZ3JMaXN0LmVuZCgpKTsKICAgICAgICAgICAgZG91YmxlIHBtZWQgPSBtZWRpYW4oY2Fnckxpc3QpOwoKICAgICAgICAgICAgcmVzdWx0cy5lbXBsYWNlX2JhY2socCwgcDE1LCBwbWluLCBwbWF4LCBwbWVkKTsKICAgICAgICB9CgogICAgICAgIHNvcnQocmVzdWx0cy5iZWdpbigpLCByZXN1bHRzLmVuZCgpLCBbXShjb25zdCBhdXRvJiBhLCBjb25zdCBhdXRvJiBiKSB7CiAgICAgICAgICAgIHJldHVybiBnZXQ8MT4oYSkgPiBnZXQ8MT4oYik7CiAgICAgICAgfSk7CgogICAgICAgIGNvdXQgPDwgZml4ZWQgPDwgc2V0cHJlY2lzaW9uKDIpOwoKICAgICAgICAvLyBTdW1tYXJ5IHRhYmxlCiAgICAgICAgY291dCA8PCAiXG5Ub3AgMiBQb3J0Zm9saW9zIFN1bW1hcnkgKEJvdHRvbSAxNXRoIFBlcmNlbnRpbGUgQ0FHUik6IiA8PCBlbmRsOwogICAgICAgIGNvdXQgPDwgbGVmdCA8PCBzZXR3KDEwKSA8PCAiIyIgPDwgc2V0dyg0MCkgPDwgIlBvcnRmb2xpbyIgPDwgc2V0dygxMCkgPDwgIlAxNSUiIDw8IHNldHcoMTApIDw8ICJNaW4iIDw8IHNldHcoMTApIDw8ICJNYXgiIDw8IHNldHcoMTApIDw8ICJNZWRpYW4iIDw8IGVuZGw7CiAgICAgICAgY291dCA8PCBzdHJpbmcoODAsICctJykgPDwgZW5kbDsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCAyICYmIGkgPCByZXN1bHRzLnNpemUoKTsgKytpKSB7CiAgICAgICAgICAgIGF1dG8gW3dlaWdodHMsIHAxNSwgcG1pbiwgcG1heCwgcG1lZF0gPSByZXN1bHRzW2ldOwogICAgICAgICAgICBzdHJpbmcgcG9ydFN0cjsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBudW1Bc3NldHM7ICsraikgewogICAgICAgICAgICAgICAgaWYgKHdlaWdodHNbal0gPiAwKSB7CiAgICAgICAgICAgICAgICAgICAgcG9ydFN0ciArPSBhc3NldE5hbWVzW2pdICsgIjoiICsgdG9fc3RyaW5nKHdlaWdodHNbal0pICsgIiUgIjsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBjb3V0IDw8IGxlZnQgPDwgc2V0dygxMCkgPDwgKGkgKyAxKSA8PCBzZXR3KDQwKSA8PCBwb3J0U3RyIDw8IHNldHcoMTApIDw8IHAxNSAqIDEwMCA8PCBzZXR3KDEwKSA8PCBwbWluICogMTAwIDw8IHNldHcoMTApIDw8IHBtYXggKiAxMDAgPDwgc2V0dygxMCkgPDwgcG1lZCAqIDEwMCA8PCBlbmRsOwogICAgICAgIH0KCiAgICAgICAgLy8gLy8gRGV0YWlsZWQgYnJlYWtkb3duCiAgICAgICAgLy8gZm9yIChpbnQgaSA9IDA7IGkgPCAyICYmIGkgPCByZXN1bHRzLnNpemUoKTsgKytpKSB7CiAgICAgICAgLy8gICAgIGF1dG8gW3dlaWdodHMsIHAxNSwgcG1pbiwgcG1heCwgcG1lZF0gPSByZXN1bHRzW2ldOwogICAgICAgIC8vICAgICBjb3V0IDw8ICJcblBvcnRmb2xpbyAiIDw8IChpICsgMSkgPDwgIjpcbiI7CiAgICAgICAgLy8gICAgIGNvdXQgPDwgbGVmdCA8PCBzZXR3KDE1KSA8PCAiQXNzZXQiIDw8IHNldHcoMTApIDw8ICJXZWlnaHRcbiI7CiAgICAgICAgLy8gICAgIGNvdXQgPDwgIi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS1cbiI7CiAgICAgICAgLy8gICAgIGZvciAoaW50IGogPSAwOyBqIDwgbnVtQXNzZXRzOyArK2opIHsKICAgICAgICAvLyAgICAgICAgIGlmICh3ZWlnaHRzW2pdID4gMCkgewogICAgICAgIC8vICAgICAgICAgICAgIGNvdXQgPDwgbGVmdCA8PCBzZXR3KDE1KSA8PCBhc3NldE5hbWVzW2pdIDw8IHNldHcoMTApIDw8IHdlaWdodHNbal0gPDwgIlxuIjsKICAgICAgICAvLyAgICAgICAgIH0KICAgICAgICAvLyAgICAgfQogICAgICAgIC8vICAgICBjb3V0IDw8ICItLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tXG4iOwogICAgICAgIC8vICAgICBjb3V0IDw8ICJCb3R0b20gMTV0aCAlIENBR1IgOiAiIDw8IHAxNSAqIDEwMCA8PCAiJVxuIjsKICAgICAgICAvLyAgICAgY291dCA8PCAiTWluIENBR1IgICAgICAgICAgIDogIiA8PCBwbWluICogMTAwIDw8ICIlXG4iOwogICAgICAgIC8vICAgICBjb3V0IDw8ICJNYXggQ0FHUiAgICAgICAgICAgOiAiIDw8IHBtYXggKiAxMDAgPDwgIiVcbiI7CiAgICAgICAgLy8gICAgIGNvdXQgPDwgIk1lZGlhbiBDQUdSICAgICAgICA6ICIgPDwgcG1lZCAqIDEwMCA8PCAiJVxuIjsKICAgICAgICAvLyB9CiAgICB9CgogICAgcmV0dXJuIDA7Cn0K