Understanding the Impact of Passing by Value vs. Reference in C++

When writing C++ code, one of the fundamental decisions you have to make is whether to pass arguments by value or by reference. This choice can have significant implications on the performance and behavior of your code. In this blog post, we will explore the differences between these two approaches, using a practical example to illustrate the impact.

The Problem: Constructing a Binary Tree (https://leetcode.com/problems/create-binary-tree-from-descriptions)

Let’s consider a problem where we need to construct a binary tree from a set of parent-child relationships. Each relationship is represented as a vector of three integers: the parent node, the child node, and a boolean indicating whether the child is a left child.

Here’s the correct solution of the problem:

class Solution {
public:
    TreeNode* constructTree(int val, unordered_map<int, vector<pair<int, bool>>> &child) {
        TreeNode* node = new TreeNode(val);
        if (child.find(val) != child.end()) {
            for(auto itr: child[val]) {
                if (itr.second) {
                    node -> left = constructTree(itr.first, child);
                } else {
                    node -> right = constructTree(itr.first, child);
                }
            }
        }
        return node;
    }
    TreeNode* createBinaryTree(vector<vector<int>>& d) {
        unordered_set<int> parentCount;
        unordered_set<int> childCount;
        unordered_map<int, vector<pair<int, bool>>> child;
        int rootVal = 0;
        for (int i = 0; i < d.size(); i++) {
            int a = d[i][0], b = d[i][1], c = d[i][2];
            parentCount.insert(a);
            childCount.insert(b);
            child[d[i][0]].push_back({b, c});
        }

        for(auto itr: parentCount) {
            if (!childCount.contains(itr)) {
                rootVal = itr;
                break;
            }
        }
        return constructTree(rootVal, child);
    }
};

The Key Difference: Passing by Value vs. Reference

In the `constructTree` function, we initially passed the `unordered_map` by value:

TreeNode* constructTree(int val, unordered_map<int, vector<pair<int, bool>>> child) {
 // Function implementation
}

This approach created a new copy of the map every time `constructTree` was called, which is highly inefficient. By contrast, passing by reference avoids this unnecessary copying:

TreeNode* constructTree(int val, unordered_map<int, vector<pair<int, bool>>>& child) {
 // Function implementation
}

Why Passing by Reference Matters

1. Performance: When you pass a large data structure by value, you create a copy of it. This can be expensive in terms of both time and memory. In our example, copying the `unordered_map` in every recursive call caused significant slowdowns, making the code run in about 2000ms for some test cases.

2. Correctness: Passing by reference ensures that all changes to the data structure within the function affect the original structure. This is crucial when multiple parts of your program need to work with the same data.

Performance Comparison

Let’s compare the performance of the two approaches using the example of constructing a binary tree. Here’s a summary:

Example TestCase(Add below test case in the leetcode add tests section):

[[81663,58322,1],[96768,33207,1],[92916,40459,0],[22620,37389,1],[65347,74076,1],[58785,61486,1],[14236,98817,1],[528,2333,1],[42189,28016,0],[22798,28503,1],[79077,72719,0],[23573,57749,1],[4294,15783,0],[13422,21696,1],[57736,88032,0],[83077,36241,0],[88553,51966,0],[58709,6008,1],[41593,42682,0],[7747,99208,0],[64456,12641,0],[34868,98197,1],[34523,47298,1],[54958,83789,1],[81413,52326,0],[85601,5443,1],[53132,82918,1],[6554,38613,0],[98218,13442,1],[3368,16059,1],[17801,28129,1],[54610,84850,1],[49171,22662,1],[57800,23592,0],[64143,3827,0],[43600,38736,1],[74314,83586,0],[2036,91583,0],[15482,19924,0],[17967,65102,1],[2109,94013,1],[9682,40069,0],[1602,33502,1],[6017,13552,1],[60020,56070,1],[31435,88396,1],[96953,68980,1],[88267,63348,0],[4141,76755,1],[46794,34192,0],[54187,86972,0],[54610,82957,0],[10225,44689,0],[77335,73950,1],[73910,30519,0],[60079,11648,0],[18662,7833,1],[20589,36211,0],[97992,57800,1],[54967,62513,1],[67395,58879,0],[9270,65030,1],[8949,28711,1],[71669,22461,1],[84100,76802,1],[81756,82669,0],[7833,1643,1],[10537,62035,1],[47451,48688,0],[50480,79947,1],[31437,97941,0],[49184,28653,0],[23124,96790,0],[2193,94176,0],[60697,34459,1],[89990,37683,0],[30215,5378,1],[91645,67356,0],[42826,27608,1],[54373,43449,1],[83803,67138,0],[32093,31872,1],[84950,19667,1],[26520,17265,0],[37601,62990,1],[99291,37292,1],[34380,25688,1],[75578,26520,1],[60898,74628,0],[55480,88765,0],[60158,58329,1],[15910,93671,0],[80341,86645,0],[71536,54828,1],[20879,48319,1],[50724,85405,0],[73763,57715,1],[99624,3902,1],[95043,16485,1],[61472,61322,1],[39755,57179,0],[21158,36025,0],[37372,19196,0],[67700,55601,0],[35596,59397,1],[36452,69125,0],[23722,44909,1],[92916,21368,1],[33913,37715,1],[39755,19302,1],[7871,17967,0],[238,65347,1],[57198,25347,1],[77845,43956,0],[21470,21375,0],[25227,74635,0],[34455,69682,0],[57892,16236,1],[86603,4515,0],[91047,73723,1],[4727,77114,1],[834,25340,1],[36021,53906,0],[5452,55470,1],[99537,85364,1],[2752,74712,1],[9762,4701,0],[88506,77339,0],[57675,15482,0],[59283,38493,0],[30089,15501,1],[56539,52753,0],[80707,57146,0],[88337,20053,1],[19461,77411,1],[91643,64257,0],[32831,17417,1],[40486,64607,0],[52615,36683,1],[1546,84457,0],[7616,3218,1],[20053,20386,0],[81253,76117,0],[211,33307,1],[58237,49218,1],[98097,27794,1],[35301,27571,0],[35318,59269,0],[18363,58990,1],[57190,21293,0],[7968,21129,0],[71915,12067,0],[62276,58785,0],[16738,98040,1],[45039,90038,1],[8184,18300,0],[1169,50246,1],[98090,62683,0],[84932,87782,1],[61383,57675,1],[89557,74804,1],[52661,18667,0],[98106,11378,0],[94508,5934,1],[18300,59296,1],[68253,34597,0],[41657,65980,1],[68562,56242,0],[69159,36799,1],[77533,15377,1],[12924,70253,1],[34261,85601,1],[37627,70174,1],[168,24951,0],[39653,53403,1],[4217,81069,1],[49500,92106,0],[81253,8526,1],[89727,51448,0],[4385,77281,1],[32438,3047,0],[89341,18158,0],[6695,30445,1],[206,34523,1],[3277,95854,1],[98775,59234,1],[3047,70092,0],[5524,4141,1],[91304,87679,1],[49723,85228,0],[42098,46290,1],[28860,67151,1],[95944,46751,1],[64566,82348,0],[46482,62692,0],[3318,56203,0],[7443,62656,0],[37537,34374,0],[61472,36719,0],[70724,81795,0],[16090,75611,1],[60128,24853,0],[17619,51309,0],[7745,8887,0],[75255,91304,0],[76530,46216,1],[4440,63031,0],[57410,51734,0],[29204,49433,0],[65705,26849,1],[88017,44197,0],[69131,84434,0],[90477,19017,1],[74403,58272,1],[46722,72422,1],[48780,49947,0],[81193,7747,0],[54730,13027,1],[31345,87012,1],[98909,12997,0],[62596,78120,0],[44707,14813,0],[23140,77996,0],[27663,25084,1],[14924,24652,1],[4307,12478,1],[34916,44063,1],[3333,95279,0],[3094,23956,1],[82066,86884,0],[17808,91226,0],[947,15570,0],[25708,56015,1],[80762,20726,0],[54967,95116,0],[41746,66090,0],[84164,28292,0],[49957,32589,1],[9682,68253,1],[43284,18397,1],[35933,30089,1],[56621,9275,0],[17579,28943,1],[2635,73447,1],[64938,29204,1],[168,23864,1],[3277,43236,0],[46621,803,0],[94992,12445,0],[7624,80195,1],[47003,44103,0],[26053,63060,1],[10889,36280,1],[46751,4836,0],[40796,63643,0],[88096,85086,0],[31933,82181,1],[86645,65464,0],[78977,46800,1],[87101,83396,1],[66317,4117,0],[62292,70672,1],[40350,2899,0],[89055,24716,1],[23862,76558,0],[25618,68015,1],[16261,28860,1],[87101,97926,0],[60956,11667,0],[56070,49723,1],[12400,6638,0],[80018,17080,1],[6730,57394,0],[79273,78304,1],[59552,78977,0],[21368,46462,1],[42404,7494,1],[2193,43874,1],[95494,17294,0],[70310,36860,1],[96626,95544,1],[18662,45302,0],[20626,97547,0],[81811,60469,1],[59296,63277,1],[47298,60702,1],[34597,72576,1],[19323,11567,1],[64607,61171,1],[60794,50888,0],[8505,27271,0],[67835,23862,0],[76117,29640,1],[38221,91153,0],[46757,41870,0],[528,50870,0],[7189,26147,0],[50592,1131,1],[21506,13323,0],[39970,84771,1],[38079,58709,1],[16608,61521,1],[95292,20626,1],[30519,70431,1],[54359,69916,1],[38319,40046,0],[47052,55792,1],[8662,23261,0],[88774,50651,0],[4948,18430,0],[19073,60020,1],[75399,38746,1],[22756,8562,1],[3428,94794,1],[78051,32039,0],[42404,86564,0],[99018,41371,0],[17801,81759,0],[29783,40026,0],[79199,89297,1],[98925,30025,0],[36500,53963,0],[79636,98554,0],[58322,48910,0],[50247,25637,0],[37901,24021,1],[97849,37537,0],[3428,24073,0],[61091,30902,0],[77932,33863,1],[55185,56678,0],[9179,74954,1],[60333,74372,1],[46770,59939,0],[14418,47786,0],[40761,77953,0],[70724,11756,1],[73262,80762,0],[35933,31496,0],[94330,48709,0],[61748,51656,1],[65806,21107,0],[29763,57892,1],[17417,28464,0],[8184,31871,1],[86335,97210,0],[81248,36021,0],[11667,2170,0],[16059,11750,1],[59216,60049,0],[13147,52673,1],[78643,83514,1],[59828,73253,1],[3950,22592,0],[65806,63435,1],[16203,44084,0],[63464,73638,0],[57491,67569,1],[99369,75734,0],[2218,76359,1],[51307,89692,0],[83396,78831,1],[97210,40219,0],[70166,20803,1],[16197,92723,0],[59442,72416,0],[79383,59712,1],[93715,92091,0],[14904,62605,1],[57116,9501,1],[71413,3315,0],[38319,206,1],[93377,26287,1],[59162,278,0],[70307,32183,0],[10439,31776,1],[2471,55742,0],[37208,54473,0],[23124,38240,1],[61206,3679,0],[91231,47578,1],[10004,80816,1],[88963,96189,1],[97992,57198,0],[5493,86199,1],[88096,19948,1],[37429,4174,0],[78958,52136,0],[61584,84804,0],[92386,21150,1],[39872,24969,0],[86401,97426,1],[31437,65820,1],[39553,82316,1],[48018,93902,1],[56202,82306,0],[68514,27809,1],[74727,73958,0],[13688,3797,1],[96618,41384,0],[83039,59022,0],[27050,35591,0],[48763,94745,0],[67798,60794,1],[19585,34911,1],[68253,97376,1],[86704,56202,1],[12390,44660,0],[48319,85905,0],[12336,73374,1],[17264,69549,1],[82956,88908,1],[74257,83851,0],[41305,63706,0],[5934,89252,1],[49797,59573,1],[76415,3287,1],[33385,35431,0],[53906,49500,0],[69556,91055,1],[51392,21618,1],[18308,56672,1],[59856,15687,1],[803,53189,0],[2715,22019,0],[62264,83352,1],[73805,72075,0],[82066,26608,1],[75629,5098,0],[87840,17130,1],[30536,69103,0],[89959,38291,1],[11857,71890,0],[71413,65402,1],[28503,2086,0],[95702,83905,1],[12400,99430,1],[8427,86202,0],[19323,6533,0],[68693,13256,1],[80139,11122,1],[54893,52052,0],[49226,96527,1],[12882,62897,1],[844,30215,0],[12627,58718,0],[75324,93495,0],[22251,9598,0],[79264,92538,0],[90616,30348,0],[84491,66327,1],[28816,24522,1],[2752,11517,0],[81135,10878,1],[75765,20748,1],[3679,95043,0],[67258,95865,1],[11002,70195,0],[79936,72087,0],[96489,39724,0],[82319,74638,1],[40758,39902,0],[75399,36098,0],[26517,76092,0],[25206,76403,0],[44530,84675,0],[9663,27347,1],[34192,33206,0],[79179,57116,1],[27707,15375,1],[35993,5227,1],[67835,80521,1],[35397,93920,1],[35802,41657,0],[54245,80341,0],[15501,82706,0],[24938,41910,0],[32506,97638,0],[6962,43284,1],[90762,57955,0],[27571,99039,1],[674,13147,1],[34975,31435,0],[90123,94613,1],[11422,60040,0],[91004,31551,1],[58577,24068,0],[42553,69159,1],[88899,32831,0],[71758,3822,0],[18705,91798,1],[61143,73124,0],[80750,72788,1],[46979,74686,1],[19757,44389,1],[27195,19602,1],[22662,22788,0],[16723,44707,1],[36241,90877,1],[24073,98234,0],[46751,89517,1],[27379,77335,0],[53021,51263,0],[96631,57736,0],[9166,49957,0],[15478,54730,0],[80521,7858,0],[33502,48924,1],[30765,70772,0],[85086,16090,1],[35215,88287,0],[84864,20305,0],[89928,32514,0],[12641,11191,1],[30190,13699,0],[59434,50377,1],[40486,20683,1],[94327,41456,1],[94230,51550,1],[78958,92145,1],[47247,2218,1],[46383,39653,1],[6244,46930,1],[89904,74969,1],[19408,88360,0],[16956,6695,1],[56408,29415,0],[75781,52192,1],[95358,59283,0],[12837,75793,0],[99624,99514,0],[62897,57514,0],[93495,6730,0],[79187,11720,1],[34192,44530,1],[64790,75366,0],[6682,79187,1],[474,13097,0],[12723,99161,1],[99161,76709,1],[5965,78001,1],[27846,72773,1],[31872,97690,0],[86794,47476,0],[27420,3397,0],[89671,88258,0],[77704,13326,1],[86868,6987,0],[81783,20792,0],[63643,75357,1],[35092,93810,0],[57426,86794,1],[84804,69686,0],[14904,22997,0],[45799,18347,0],[58036,39872,0],[94613,26454,1],[52183,62160,0],[14210,57305,0],[54212,94685,0],[74257,38908,1],[66730,19073,1],[13323,41897,1],[57892,16375,0],[72158,35578,0],[62544,81173,0],[83039,52661,1],[96819,53404,0],[13699,42390,0],[17485,54245,1],[80740,11326,1],[88267,71220,1],[13917,46979,1],[80512,3277,0],[27334,70873,1],[17485,28342,0],[89692,42679,0],[6638,57496,0],[95049,8553,0],[57254,87008,1],[28096,20287,1],[80139,57548,0],[20683,81831,0],[56408,61807,1],[4141,96093,0],[46800,57410,1],[87679,22585,1],[11958,72495,1],[38493,39249,0],[58119,78865,0],[24938,28529,1],[77083,50195,1],[52497,3124,1],[44358,64456,1],[99430,46383,0],[11720,9270,1],[9172,35319,1],[73449,50382,0],[54185,11681,0],[11958,15453,0],[12388,72701,0],[65820,89671,0],[95860,19961,1],[83803,51714,1],[78850,40087,0],[66124,64765,0],[98156,85865,0],[10307,60074,0],[92538,90893,0],[61486,4741,1],[90373,17217,1],[67431,92777,1],[36919,15205,0],[20726,65392,0],[21779,26943,0],[27678,95585,0],[42434,80704,0],[50703,98155,0],[76505,21158,0],[72285,33714,1],[89353,91480,1],[51448,12388,1],[11567,79383,1],[57022,62307,1],[64683,89597,1],[66237,82034,1],[25635,39207,0],[14956,10227,1],[61236,88148,0],[40838,25206,1],[49197,96146,1],[57116,81881,0],[57800,67739,1],[72966,6554,1],[11039,72729,0],[30215,36350,0],[13256,85117,0],[84055,56981,1],[89928,68594,1],[39929,68629,0],[90038,14822,1],[90893,51486,0],[85403,20617,1],[9072,79936,1],[32039,80989,1],[947,81430,1],[9598,78523,1],[75192,25485,0],[14813,36137,1],[54550,12238,1],[93902,16197,1],[82684,11639,1],[47341,28816,0],[90877,17579,0],[7080,37458,0],[88765,82110,1],[53432,98610,1],[57305,60158,1],[70657,93377,0],[50285,38720,0],[37371,18610,1],[24716,74974,0],[44915,49000,0],[15687,16266,0],[26154,34249,0],[61806,91564,0],[34945,94878,0],[11191,79013,0],[26852,52629,0],[29204,79959,1],[69556,92479,0],[41946,18662,1],[44328,40758,1],[25460,9762,0],[92723,96706,0],[2468,47052,1],[24652,57671,0],[8524,90725,1],[20195,87840,0],[37797,41746,1],[80191,66617,1],[49533,10681,0],[24021,64938,1],[10685,67700,1],[53472,77653,0],[22997,58592,1],[4316,79179,0],[59216,49197,1],[59022,39147,0],[71220,37372,1],[91172,21470,1],[15601,17034,1],[41305,37653,1],[46462,80282,0],[77904,75047,0],[17401,63062,1],[23804,28427,0],[81230,22875,1],[91564,44755,0],[67518,37576,1],[25861,32093,1],[90519,76949,1],[87679,56252,0],[59397,94632,1],[37968,534,0],[51448,42189,0],[39597,98877,1],[93377,67167,0],[4086,8439,1],[42682,34183,1],[49709,3480,0],[10685,95758,0],[42854,62872,0],[84785,66645,1],[23035,32949,1],[83209,34975,0],[18837,44358,1],[88287,66370,0],[12373,17109,1],[85158,70616,0],[11694,16956,0],[28292,6991,1],[49218,34654,0],[87840,42863,0],[95494,24938,1],[12723,96768,0],[25306,55869,1],[18692,18930,1],[8271,25180,1],[97011,58626,0],[86335,56408,1],[26146,10307,1],[14287,71915,1],[68486,46438,1],[7428,25708,0],[95443,6451,0],[59434,82519,0],[37680,1554,0],[30528,73449,1],[36123,98156,1],[69356,96310,0],[48365,22251,0],[52488,7941,1],[34843,7185,1],[13699,35318,1],[25180,8373,1],[29314,69052,0],[2468,29790,0],[98817,91289,0],[61571,89255,0],[93564,474,1],[9493,77715,1],[13011,36212,0],[58626,95443,1],[61143,55264,1],[52052,35622,0],[46594,30412,0],[38079,89618,0],[40459,86045,0],[58782,43853,0],[64367,69110,1],[36334,7299,0],[3294,42098,1],[72285,47502,0],[28663,24834,1],[14032,78032,1],[25306,47003,0],[59507,61143,0],[10166,4755,0],[47483,7726,1],[25133,80572,1],[89182,84088,1],[91226,80018,0],[41910,16753,1],[12388,5493,1],[60158,50247,0],[11422,99851,1],[816,18089,1],[31759,45248,0],[16565,19829,0],[11750,94157,1],[3635,73736,1],[77487,1546,1],[34654,37968,1],[4741,87287,0],[69549,81511,1],[29980,16187,0],[14032,57868,0],[23027,70828,1],[95944,60805,0],[67127,81135,1],[85601,89368,0],[33279,58840,1],[32930,71881,0],[81610,24415,1],[2166,96420,0],[63062,21057,1],[8797,2711,1],[62692,99788,0],[38908,52622,1],[91798,75588,1],[35549,91645,1],[78001,31933,0],[10681,41526,0],[50108,17955,0],[7616,68562,0],[86794,11857,1],[25688,94964,0],[54033,96795,1],[53698,10004,1],[75075,43719,1],[49433,11055,1],[84785,1647,0],[84809,73841,1],[86481,7041,0],[35578,10750,1],[32514,21753,1],[14985,1480,1],[4701,97720,1],[38040,63973,0],[84771,91047,1],[91172,33853,0],[44358,75324,0],[76669,25306,1],[18323,72430,0],[37186,15041,1],[5965,42434,0],[65676,58569,1],[52194,12400,0],[31135,64566,1],[22824,16261,0],[47708,13897,1],[80802,64513,0],[25639,52904,1],[58785,682,0],[63707,74669,0],[81795,27105,1],[348,54346,0],[27788,36932,1],[92060,84971,1],[94992,80750,1],[23592,63028,1],[80925,94040,1],[3047,71758,1],[82956,13012,0],[86708,47089,0],[93830,3950,1],[37389,64443,1],[96310,28102,0],[68693,52497,0],[12694,67736,1],[76884,49521,0],[84491,37183,0],[68514,3529,0],[27678,61206,1],[53578,39559,0],[76505,17636,1],[44707,38079,1],[65791,20710,1],[20683,3094,1],[73124,49866,0],[38613,40498,0],[95893,94952,1],[73124,5329,1],[95965,9493,1],[36211,98116,0],[36350,99879,1],[21057,42978,1],[44373,93954,0],[98775,92060,0],[84932,83039,0],[48763,74267,1],[74638,9289,0],[39872,31135,1],[46046,29414,1],[36137,62276,1],[36585,5460,0],[69460,46093,0],[4836,10537,0],[51263,17066,1],[27520,18469,1],[12445,51307,1],[16714,35993,1],[64456,8427,1],[53472,75543,1],[72470,13688,0],[95865,23515,0],[51183,64806,0],[33502,98925,0],[4643,39133,1],[94685,2036,1],[7666,22996,1],[22662,21807,1],[27794,42854,0],[49866,27707,1],[90931,53021,1],[31247,61571,0],[72430,64683,0],[57548,58295,1],[94231,32419,0],[52622,13316,1],[72075,55565,1],[39970,87927,0],[78870,98426,1],[61521,99102,0],[75495,64694,0],[19089,7189,0],[93210,17920,1],[63542,10343,1],[58569,55185,1],[24853,81114,0],[12882,57022,0],[8553,84932,0],[77253,85755,1],[682,94531,1],[16173,84092,1],[39249,98110,0],[60217,50287,1],[24021,34087,0],[5378,18617,1],[2899,63496,0],[31337,94991,0],[46207,77283,0],[93210,92758,0],[19408,44608,1],[91223,18971,1],[99161,26517,0],[65392,5005,0],[21470,68399,1],[18742,78382,1],[42346,92339,1],[99788,56625,0],[35596,91643,0],[18667,31337,0],[45400,84329,0],[41946,40506,0],[65742,4679,1],[31345,2166,0],[57543,53708,1],[75357,19465,1],[2069,61236,0],[34654,29980,0],[81248,44135,1],[97376,94092,0],[5317,77225,0],[43236,9028,0],[99514,816,1],[7363,83733,0],[75765,90603,0],[63963,40486,0],[278,16714,1],[80572,27050,0],[87210,57635,0],[67151,49184,1],[51745,73185,0],[62041,23258,1],[87169,41593,0],[92192,89904,0],[93592,51407,0],[40838,59856,0],[58322,15650,1],[7080,69167,1],[53698,46482,0],[13046,31523,0],[32882,8476,1],[25755,92889,1],[96512,38306,1],[66568,93394,1],[15570,67855,1],[92729,46207,0],[65763,5332,1],[13326,31759,0],[88908,14985,0],[67148,98713,0],[20386,53349,0],[78761,62292,1],[85228,92344,0],[93830,68771,0],[92885,36741,0],[73387,56858,1],[98116,13011,1],[82717,9663,1],[71814,90519,1],[7872,23655,1],[75366,74685,0],[38736,98135,0],[13011,77704,1],[57671,38221,0],[94330,22549,1],[46222,49673,1],[57395,75148,0],[47578,93592,1],[75626,53610,1],[26520,36972,1],[67138,64699,1],[53963,6687,1],[57765,99624,1],[73331,32438,1],[28435,5054,0],[82717,76530,0],[22777,94647,1],[59617,42553,0],[54112,32506,1],[95758,2653,1],[66337,7653,1],[56768,62963,0],[8827,27663,1],[53879,31247,1],[26000,47341,0],[19196,35397,0],[16710,29680,0],[21572,58966,1],[63847,91177,0],[91583,89727,0],[96768,96801,0],[29790,67699,0],[42434,68634,1],[68634,72470,1],[31871,17401,0],[57343,89247,1],[40026,49533,0],[81862,89928,0],[87008,87057,0],[76530,69257,0],[88258,91223,1],[24209,78870,1],[27846,41086,0],[25460,9172,1],[41075,6184,0],[58569,57190,0],[19985,76199,0],[40814,77215,1],[5947,1948,1],[14813,84491,0],[88506,22756,1],[1912,73500,1],[77903,91261,1],[37968,73387,1],[88612,4798,0],[98319,34868,0],[84164,58895,1],[37354,66730,1],[12791,46046,0],[68980,68296,0],[59154,95413,0],[99918,35612,1],[64524,69356,0],[85905,69131,0],[76593,50592,0],[18808,99291,0],[59479,46740,1],[92843,37168,0],[90762,64143,1],[28884,74512,1],[57644,1684,0],[13897,51497,0],[13688,55619,0],[98713,23768,1],[25708,28879,0],[54983,97306,0],[52318,50521,0],[44103,13221,1],[10750,60217,1],[96631,97837,1],[36334,16203,1],[7494,57579,1],[17778,43246,0],[65832,33011,1],[5014,43600,0],[28529,79849,1],[69159,44424,0],[20748,22790,0],[63435,55412,1],[26146,70490,0],[77114,1912,0],[33696,48749,0],[37527,37627,0],[5928,13799,0],[89517,48763,1],[43634,18545,1],[91231,99369,0],[79636,86335,1],[46621,75075,1],[5493,92669,0],[11489,32355,1],[69711,81262,0],[35591,77945,1],[78560,20160,0],[93920,23722,1],[72416,75192,1],[70828,7672,0],[93810,40761,0],[27817,56539,1],[32882,27817,0],[34087,19809,0],[50651,36148,1],[98116,12723,0],[18808,82962,1],[63963,12373,1],[96723,56711,1],[3902,42760,0],[60480,73093,1],[72327,68679,0],[48619,55415,1],[85456,27891,0],[88765,62211,0],[70893,51392,0],[67311,12162,0],[92829,77005,0],[74733,81756,1],[98480,83696,1],[32475,65554,1],[92723,27520,1],[84542,29398,0],[71434,15775,0],[3679,82684,1],[84457,5928,0],[86401,68445,0],[90603,70518,0],[58329,82449,1],[94368,51420,0],[42843,51301,0],[47871,80842,0],[47773,74727,0],[50285,86868,1],[28129,47708,0],[90893,9640,1],[64524,49190,1],[38720,54967,1],[21659,7131,0],[24652,99638,1],[52753,34261,0],[43956,44907,1],[28605,4217,1],[65305,18692,1],[49521,22798,1],[7871,92729,1],[25794,2193,0],[76359,75495,0],[62897,924,1],[4515,16347,1],[84318,96819,1],[72416,13220,0],[50382,97399,1],[17222,97560,0],[33853,84586,0],[19602,53675,1],[99931,62231,0],[16197,6017,1],[24567,27334,0],[41390,74891,0],[52194,41946,1],[56981,78504,0],[23888,17742,0],[40046,54550,1],[10750,63464,0],[81417,56768,0],[8197,68204,1],[75192,65806,1],[27278,11489,1],[5014,18705,1],[37186,46298,0],[12641,32048,0],[76101,98909,1],[63463,82260,0],[55869,3333,0],[71754,23400,1],[98009,13802,1],[70195,3436,1],[18971,99222,1],[5378,83242,0],[53228,88267,0],[18423,17801,0],[64143,12714,1],[74974,29763,0],[13027,16565,0],[65396,76101,0],[91513,72387,0],[3368,89353,0],[11687,15163,0],[49533,59617,1],[73910,23035,1],[18735,16608,0],[9640,38040,0],[32093,39838,0],[66660,70307,1],[71754,1602,0],[46740,91536,1],[20053,79816,1],[57765,94508,0],[59397,17222,0],[4523,99463,1],[95860,25070,0],[57426,19461,0],[30465,23800,1],[1480,36355,0],[76400,32993,1],[15478,27083,1],[88899,70893,1],[70590,92192,0],[48688,8348,1],[54958,89501,0],[28464,89546,0],[80018,17161,0],[5934,800,0],[94685,50703,0],[33816,70310,0],[67127,52488,0],[91798,75988,0],[49500,32518,1],[53404,20589,1],[13256,99753,1],[70873,74946,0],[26085,14362,1],[22824,7871,1],[58782,16503,1],[72158,92820,1],[49694,25227,1],[53906,76587,1],[14956,58036,0],[19961,19478,0],[69125,95847,0],[24068,50487,1],[98026,56778,0],[85158,33831,1],[79187,57446,0],[82985,45132,0],[69209,39654,1],[77750,19985,1],[90519,58589,0],[78865,77329,1],[58701,87210,0],[48018,7666,0],[4080,60329,1],[91643,3021,1],[69141,40907,1],[83209,55762,1],[9985,68313,0],[56625,87205,0],[15453,27196,0],[44103,2752,0],[10299,60079,0],[73262,82956,1],[9177,59434,1],[12694,49700,0],[25635,65771,1],[17130,1928,1],[54028,20195,0],[27817,91172,0],[9327,18071,1],[36932,27254,1],[81135,60333,0],[33816,46222,1],[18430,5461,0],[76709,81248,1],[36585,35215,1],[20803,57814,0],[24567,27788,1],[60469,17931,1],[5329,70080,1],[77225,14236,0],[41746,77401,1],[36919,16466,1],[95585,17619,1],[6638,43040,1],[25794,52747,1],[1728,38711,1],[7534,10299,1],[49242,4812,1],[95847,80283,0],[12305,96857,1],[27809,42743,1],[4798,66237,0],[78304,28096,1],[62522,6969,1],[73500,12837,1],[56854,87681,0],[18692,89557,0],[57814,40139,1],[53021,25618,1],[31871,86708,1],[74635,528,0],[95847,46770,1],[92829,40141,1],[31247,24741,1],[52326,82549,1],[22394,34521,0],[47808,77528,1],[13637,66337,0],[84329,38450,1],[75793,56345,0],[15127,80789,0],[82034,12336,0],[27050,86401,1],[49218,88337,1],[84318,9166,0],[72387,24864,1],[62491,45400,1],[6274,67258,0],[61042,67395,1],[57496,40790,1],[3294,26146,0],[15695,68514,1],[40372,41896,0],[29790,25755,1],[22592,64367,1],[85403,95633,0],[80990,62888,0],[97849,62349,1],[24716,87613,1],[58995,14418,1],[56539,55654,1],[38240,2364,1],[23864,63463,0],[27334,90839,0],[19619,70061,0],[91564,97081,1],[55513,81862,0],[70415,2538,1],[33279,51745,0],[31407,42843,1],[61070,62596,0],[92758,55491,0],[90877,69460,1],[62222,54359,1],[69125,17485,1],[4973,97011,1],[28539,98775,1],[7299,53559,0],[10681,41840,1],[18610,10190,1],[44909,90508,0],[42854,97896,1],[63643,15748,0],[90782,89752,1],[17967,27846,0],[19757,5317,0],[44761,41390,1],[87169,88506,1],[95292,31212,0],[86603,95944,1],[89252,16568,1],[59283,69736,1],[91528,8271,1],[18837,53578,0],[63765,51755,0],[19809,58889,1],[94092,37680,0],[7363,12882,1],[89597,21242,1],[33307,17201,1],[54405,18074,0],[66645,41524,0],[39553,68656,0],[81862,62041,1],[83641,84267,1],[34380,35359,0],[91981,80707,1],[41524,27195,0],[93230,97387,0],[97944,21500,1],[44412,87019,1],[27196,31085,1],[21673,94992,0],[92538,49674,1],[71814,19064,0],[69356,16146,1],[49723,29246,1],[11648,21660,1],[12935,19089,0],[12478,81832,1],[89618,46571,1],[20386,10685,1],[55742,76974,1],[47044,45574,1],[76101,34085,0],[62035,93830,1],[8476,53228,0],[37683,34380,0],[70490,28951,0],[9166,16710,1],[90373,36585,0],[47578,7616,0],[50660,94231,0],[70590,52194,1],[90891,84318,0],[86849,46757,0],[98713,67835,0],[22251,76583,1],[66956,11002,1],[1575,65676,0],[28427,54139,0],[74838,88774,1],[14236,67624,0],[82957,84864,1],[79498,58661,1],[41524,37186,1],[16963,81417,0],[1602,55798,0],[4809,92466,1],[37458,71631,0],[61383,92898,0],[52497,65705,0],[41526,53472,1],[21618,83401,1],[48924,90782,0],[17417,67112,1],[55415,48853,1],[3436,12198,1],[69460,80556,1],[6384,61274,0],[1921,11892,1],[42863,2216,1],[68594,21789,1],[18300,23747,0],[13436,66125,1],[99638,34793,1],[7335,48780,0],[52753,79264,1],[74638,15772,1],[22585,37844,0],[36972,91892,0],[77533,24651,0],[70824,12305,1],[83894,33245,1],[33223,78726,1],[81413,65763,1],[92756,88899,1],[55513,76669,1],[70310,45800,0],[64694,98916,0],[81173,40009,1],[50377,10166,0],[99369,54185,1],[59269,36919,1],[29314,25861,1],[48365,31407,1],[64367,78906,0],[99365,97310,1],[89959,90676,0],[21807,76360,1],[63277,4970,1],[91981,10677,0],[72576,96618,1],[98745,37371,1],[60020,72158,0],[82110,41238,0],[9762,72624,1],[32993,73844,0],[37599,83894,1],[98156,45359,1],[89990,33185,1],[95358,61748,1],[2109,95965,0],[11489,4307,0],[66568,71413,0],[3397,18308,1],[27788,33310,0],[56345,39574,1],[56672,2468,1],[83629,85403,0],[37527,15644,1],[75578,40796,0],[10240,29620,0],[11917,28884,0],[51755,61021,0],[37797,98480,0],[80191,63765,0],[32630,71536,1],[39559,13489,1],[29763,88799,0],[1421,45039,0],[2364,69177,0],[69257,62104,0],[41657,4727,0],[78865,97903,0],[14130,94327,0],[2216,43144,0],[31135,67431,0],[54033,26311,0],[3094,89387,0],[93810,83666,1],[8271,42826,0],[4523,57343,0],[98745,10457,0],[89368,22120,0],[3397,87169,0],[2635,49242,0],[38736,20879,1],[94410,37479,0],[48718,95040,0],[80195,79109,0],[15375,28663,1],[75075,95222,0],[66090,26076,1],[56630,94368,1],[90508,11373,1],[7323,4387,1],[76949,13436,0],[13319,356,0],[74314,37429,1],[88612,25133,1],[39902,98218,0],[58592,65125,0],[92862,40849,0],[23768,37797,1],[32589,28203,1],[67699,54373,1],[44852,4294,1],[40087,89663,0],[79816,84809,1],[1647,38585,1],[15644,67244,0],[20792,7224,0],[77903,33913,0],[62035,14032,0],[75988,62717,1],[20726,66655,1],[49957,19314,0],[1342,1169,1],[35397,66568,0],[51642,81413,0],[60469,844,0],[55565,4102,1],[76415,80102,0],[49673,19585,0],[69731,95860,0],[1010,63118,0],[83894,18808,0],[12939,25594,0],[36452,72345,1],[46298,25995,0],[44862,92995,1],[16236,44862,0],[61806,98745,1],[16236,32157,1],[56070,947,0],[97941,91616,0],[34085,9072,1],[69052,14299,0],[45400,59332,1],[32518,69988,0],[34945,1359,1],[74353,32630,0],[4727,29776,0],[27379,68588,1],[98554,62222,1],[10004,95358,0],[48203,73763,1],[86469,16369,1],[85529,74048,0],[17294,69711,0],[2093,18837,0],[84850,87101,0],[72773,20772,1],[35301,3368,1],[58592,6962,1],[69846,76415,0],[43112,57644,0],[70028,86603,1],[80762,56519,1],[2216,63847,1],[2899,45226,1],[66327,48142,1],[8373,96689,0],[39147,84312,0],[11667,69318,1],[72255,99077,1],[72701,48562,0],[35578,8662,0],[91616,85529,1],[98319,11687,1],[61322,82195,0],[88032,75854,0],[61521,33385,1],[20088,35802,1],[27278,25794,0],[77329,42167,0],[39724,79010,0],[82074,12791,0],[99039,92598,0],[30465,52183,0],[99851,29295,1],[2779,49226,0],[58589,34709,0],[37683,67798,1],[5317,76631,1],[49171,14820,0],[20792,40264,1],[24651,57223,1],[89314,2728,0],[54212,96269,1],[54507,82063,0],[42682,73262,0],[67395,80191,1],[38493,13290,1],[34229,89298,0],[83791,834,1],[65046,98009,0],[5054,68173,1],[12837,81610,1],[78114,57812,1],[14822,54627,0],[54346,45926,0],[49463,71027,0],[73756,3075,1],[81811,27420,0],[24098,99516,0],[89247,70166,0],[86389,37527,1],[28129,44915,1],[11373,93988,0],[93920,69430,0],[97310,69238,0],[21107,70201,0],[20160,32022,0],[77411,84235,0],[8346,77403,1],[93566,46707,1],[57179,46435,1],[58577,75626,1],[9172,61091,0],[8553,7745,1],[47089,96723,1],[13220,46722,0],[49190,3635,1],[1728,84179,0],[2093,51642,1],[87782,73910,0],[13550,14130,1],[86389,85122,0],[39574,4643,1],[78850,1712,1],[23956,94622,0],[41870,69418,1],[51714,95146,1],[79816,2471,0],[22790,24756,0],[43051,50480,1],[45359,70783,0],[15864,17351,0],[4836,69846,1],[76631,14731,1],[53879,28539,0],[29091,48919,0],[25485,85461,0],[19017,91528,0],[94632,72803,1],[6682,98109,0],[74684,43051,0],[25995,35092,0],[56455,79541,0],[55762,82985,1],[97941,8538,1],[51936,37931,0],[73093,68504,1],[9598,35596,0],[28435,31345,1],[37599,54212,0],[94794,42430,1],[78726,70617,0],[92483,74244,0],[78051,18910,1],[83629,46359,1],[81430,31532,1],[35883,15478,0],[32589,70590,0],[66337,77099,0],[22517,42346,0],[18308,24567,0],[51321,16173,0],[55470,33372,1],[68679,21491,1],[55792,51183,0],[78831,36609,1],[60128,47121,1],[63464,54093,1],[46800,37876,0],[50247,77734,1],[92777,99537,1],[77083,5965,0],[13489,74314,0],[65347,58765,0],[36972,74032,1],[65490,37028,1],[84484,46794,1],[15570,92489,0],[74974,59442,1],[62211,36334,1],[52622,89816,0],[65980,5947,1],[73387,40386,0],[74838,42709,0],[80102,56189,1],[36719,55451,0],[1150,12649,0],[51734,65305,0],[15748,7335,0],[44328,12627,0],[25347,65046,0],[34459,50285,1],[5358,76978,1],[55185,9177,1],[62276,25460,1],[52661,93306,1],[73736,70144,0],[46359,58119,1],[38585,85105,1],[59617,92705,1],[18125,46081,1],[92729,98826,1],[33498,75629,0],[17294,83729,1],[88799,11694,0],[54028,24096,1],[42098,98848,0],[82181,81341,1],[79273,81193,0],[26454,59424,1],[29980,78761,1],[62692,22824,1],[1342,39553,0],[13012,74838,1],[96420,94044,0],[37601,85066,0],[16266,45633,0],[27195,75765,0],[17619,58662,1],[6783,348,0],[31496,69141,0],[79010,72285,0],[72577,94230,1],[7158,21572,0],[14924,52802,0],[30449,75781,1],[51497,70657,1],[46722,7130,0],[73675,49171,1],[7833,50044,0],[710,7872,1],[57198,9985,0],[36468,4550,1],[1647,59552,0],[16485,710,0],[77734,44476,0],[51486,13422,0],[53132,18735,0],[4741,17653,1],[89297,22033,0],[71220,44328,0],[70616,61070,0],[8887,75578,1],[33853,68083,1],[72495,7624,1],[19314,15910,0],[14210,54983,1],[20748,96489,1],[77845,17354,1],[80512,47871,1],[50287,413,1],[18617,82930,0],[88553,39848,1],[82918,29783,0],[30190,72255,1],[17080,18385,1],[80283,78114,0],[8887,98106,0],[64848,99918,1],[36211,53879,1],[24203,1648,1],[57644,4603,1],[40796,82066,1],[4086,66124,0],[92106,74403,0],[36609,88527,0],[82319,37093,0],[78304,43443,0],[1575,28605,1],[13489,94410,1],[37372,70642,1],[4973,57395,0],[39525,32930,1],[73185,86396,0],[22790,8524,1],[40069,5014,0],[69711,54033,1],[54366,30784,0],[91004,80512,0],[20617,10240,0],[53404,37599,0],[17217,93210,0],[31377,26085,1],[50287,85420,0],[14820,50724,0],[14820,12109,1],[63707,93694,1],[82918,32554,1],[14287,17013,0],[44689,93715,0],[65102,93566,0],[90264,79544,0],[33207,89853,0],[79199,69649,0],[54139,54356,1],[64513,88111,1],[51420,44086,1],[10677,2779,1],[89546,51936,1],[15687,28073,1],[37681,55465,0],[8338,34916,0],[11756,37681,0],[70092,16990,1],[81173,90622,0],[83573,54893,1],[68083,71451,0],[92820,61472,0],[3950,75382,1],[62872,9179,1],[91261,46594,0],[47476,2069,0],[8406,90869,1],[16710,35883,1],[16990,17690,1],[27271,69731,0],[238,34843,0],[71536,3294,0],[57635,93549,1],[45359,63,1],[81610,31749,0],[74267,69209,0],[87205,58204,0],[3797,95292,1],[4174,72327,0],[29776,59526,1],[26154,90786,1],[84100,25979,0],[24741,35184,0],[20769,11422,1],[19829,1601,1],[62717,12924,1],[24203,84484,0],[22012,11763,0],[16963,32882,1],[29680,21506,1],[42709,1421,0],[73331,64471,0],[7858,20088,1],[80572,90931,1],[73449,62264,1],[58018,85794,1],[36350,57923,0],[71915,39755,1],[52615,50660,0],[63542,82827,0],[98135,1010,0],[51307,82359,1],[60480,79273,0],[67148,23921,1],[91289,51173,1],[84088,38156,0],[76583,84164,1],[79959,54112,0],[89671,44940,1],[20769,5452,0],[4117,88963,0],[66655,77290,0],[92843,73527,1],[93230,28755,1],[37653,211,0],[70828,88553,1],[37028,6175,0],[69649,57543,0],[91528,33498,0],[71669,7443,0],[77704,91231,0],[22875,90641,1],[4812,43608,1],[8524,17327,0],[5569,10439,1],[75241,18125,0],[96790,19025,0],[50246,79077,0],[28619,58152,0],[92820,47247,1],[54245,60128,1],[17920,26000,0],[30902,84679,1],[46495,80845,0],[57749,87062,1],[85420,23801,1],[76587,78804,1],[30765,26852,1],[99788,54610,1],[43660,60903,1],[73500,93230,0],[80077,76529,0],[10227,6783,0],[30445,17778,1],[37458,46495,1],[96953,3958,0],[6533,72348,1],[19073,59828,0],[58879,14202,1],[94531,11804,1],[31759,21826,1],[25227,59507,1],[44373,61054,1],[12924,46612,0],[93306,95893,1],[75148,18306,0],[75047,80990,0],[69167,16452,1],[63435,33760,0],[65046,11039,1],[4440,48718,1],[44909,54187,1],[98090,23140,1],[5358,58622,0],[75588,91981,0],[46794,80925,1],[75382,11488,1],[87210,58160,1],[13897,47044,1],[13637,8797,1],[87613,17754,1],[9179,26678,0],[25861,60898,0],[96819,84785,1],[23921,95494,1],[74969,36123,0],[77487,43607,0],[20803,65490,1],[45248,13637,1],[98848,60061,1],[4798,40884,1],[99077,39525,1],[52673,71337,1],[96146,81358,1],[90038,61584,0],[77339,56455,0],[21129,1351,0],[86396,96626,1],[81262,18525,0],[19025,78643,1],[16565,48425,1],[2779,49463,1],[67258,38654,0],[69430,17602,1],[49674,92756,0],[62683,69264,0],[64566,77038,1],[59939,58806,1],[39724,47451,1],[99514,87055,0],[46438,75589,0],[4385,5162,0],[62491,98097,0],[52052,77533,1],[58889,86752,1],[20305,85195,1],[84312,58782,1],[56778,86481,0],[66327,4086,0],[84055,57426,0],[32554,36452,0],[62683,1150,1],[61042,14904,0],[94508,33865,0],[37168,55513,1],[60761,43634,1],[44755,18365,1],[81069,74257,1],[82827,15127,1],[25485,31590,1],[16723,71814,0],[31407,81783,0],[34597,26145,0],[84971,71551,1],[25618,65140,0],[13012,81826,0],[4316,82074,1],[25133,47483,0],[14130,39970,1],[80283,97680,1],[23541,13166,0],[93592,97992,1],[27904,64101,1],[46222,7158,0],[59856,5789,0],[25639,61020,0],[94040,90762,1],[41593,64790,1],[73950,30465,0],[77945,92136,1],[31872,79772,1],[32630,24209,0],[46482,89927,1],[45039,83209,0],[22756,19757,0],[76583,61042,0],[93694,4948,1],[37208,8406,1],[56186,3292,0],[30025,19619,1],[38450,21779,0],[55480,8184,1],[85105,33816,1],[87055,23339,1],[46093,39597,1],[54187,7534,1],[10343,68486,0],[76593,10668,1],[87055,9327,0],[47003,50108,1],[28503,90264,1],[93671,57254,0],[98026,39470,1],[70166,11958,0],[91304,73805,0],[21826,40350,1],[10457,89182,1],[24068,39492,0],[99918,98026,0],[5947,65711,0],[37292,47490,1],[75255,66660,1],[58626,85282,0],[92705,90392,0],[17920,25639,1],[19602,60697,0],[15453,17264,1],[4679,22394,1],[51183,23888,1],[20710,74684,0],[51734,54958,1],[77932,92885,0],[77225,64848,1],[98817,26942,1],[81627,47849,1],[76400,67127,0],[69736,70415,1],[64938,96631,0],[8562,4809,1],[75611,51003,0],[29783,65742,1],[66730,9682,0],[12649,79498,1],[73374,4014,1],[14841,19385,0],[12478,20083,0],[56519,89570,1],[37389,25835,0],[92145,77729,1],[15163,69499,1],[43600,39929,0],[58709,78958,0],[22019,37085,0],[81417,2093,1],[93306,84828,0],[28203,76884,1],[99879,49010,1],[81759,22012,0],[34459,2109,0],[6017,78051,0],[67739,34525,1],[6783,78560,1],[15601,54933,0],[1169,72577,0],[59507,30528,1],[51642,8197,1],[75854,92386,0],[83789,97944,1],[35318,99931,1],[25979,45683,1],[80707,6682,1],[62307,71434,0],[79947,3318,0],[27271,23541,1],[20589,70028,1],[40372,37222,1],[44608,73193,1],[2333,73756,1],[40069,88017,1],[32554,91004,1],[67311,85593,1],[43607,55480,1],[28711,93653,0],[33831,22869,0],[57410,65610,1],[33207,83077,1],[60805,4385,1],[30528,70724,0],[63348,25635,1],[83242,30513,0],[72255,84542,0],[53228,58237,1],[88908,97849,1],[17217,77932,1],[84484,99018,0],[82074,61401,1],[17931,74353,1],[55654,92829,0],[94044,58991,0],[59552,98319,1],[95049,70782,1],[82549,82472,0],[56630,15601,0],[59022,29314,1],[35883,31437,1],[816,2864,0],[2218,26081,0],[60761,37686,0],[75324,62522,1],[65820,1575,1],[52192,36519,0],[74733,30449,0],[1684,62544,0],[95585,70945,0],[94647,76505,0],[15748,8924,1],[21506,58995,1],[82034,72966,1],[2170,42911,1],[58237,8505,0],[62717,57765,0],[94368,7363,1],[40026,54507,1],[47483,83701,0],[844,21673,1],[81759,23573,1],[33760,92862,0],[20772,47773,1],[54730,53698,0],[46298,62491,1],[20160,93644,1],[8505,65396,1],[4643,93299,0],[2036,19323,1],[23956,59216,1],[4217,96953,0],[44197,46621,1],[67798,26154,0],[98155,40372,1],[92889,21659,0],[73638,28619,1],[8662,63707,1],[20195,53132,1],[83729,7968,1],[85105,63963,0],[96489,81627,1],[37028,79636,1],[24209,27278,0],[4448,79567,0],[92889,10533,1],[42863,48018,0],[23027,23804,0],[7672,60286,0],[47871,8068,1],[33865,28435,1],[37901,41305,0],[7666,27379,0],[25070,19515,1],[78977,95049,0],[55491,15386,0],[60805,5569,0],[73675,29648,0],[6175,9191,1],[21789,59479,0],[68634,15269,0],[37715,51683,0],[22777,15695,0],[83586,43149,1],[356,65057,0],[78726,33325,1],[51241,67790,0],[72348,80020,1],[74712,30765,0],[19196,23027,1],[23800,95212,1],[59845,71645,0],[21660,74971,1],[37876,5358,1],[69731,80802,1],[89904,40455,0],[82549,93345,1],[62349,59154,0],[76974,82958,1],[60898,70715,1],[13802,12260,0],[97011,87604,1],[7745,30190,1],[1480,70824,1],[682,82717,0],[61020,31970,0],[15205,89959,1],[90508,1921,0],[10002,48365,1],[25206,98074,1],[55869,80077,1],[83396,39750,0],[63060,53210,1],[16347,78402,0],[58662,91513,0],[96801,85450,1],[16187,47808,0],[26849,70295,0],[76631,51241,0],[3797,36524,0],[85066,36500,1],[35802,86849,1],[87604,70325,0],[96689,72766,0],[42911,14101,0],[88148,13319,1],[51550,55866,0],[39929,92916,1],[37876,77253,0],[30536,65975,1],[35092,82309,1],[15041,8949,0],[43607,81663,0],[46207,8346,1],[50195,33696,1],[79544,20769,1],[73527,16723,1],[38711,40777,1],[70325,90907,0],[28539,90116,0],[18667,54366,1],[68562,32475,1],[23768,5524,0],[65602,4973,0],[12997,61484,0],[62349,69556,1],[16347,40085,1],[81193,34229,1],[78504,36324,0],[34183,87219,0],[24096,16963,0],[4755,83585,1],[34374,21921,0],[74032,36234,0],[7131,85456,0],[56455,73368,1],[2086,54405,1],[87782,77750,1],[41897,24925,0],[59479,84100,0],[92106,31377,1],[91153,65832,0],[59424,238,1],[22996,21163,0],[99102,39093,0],[92756,76593,0],[46495,44412,1],[70782,37901,1],[89663,48535,0],[61206,16738,1],[16375,78519,0],[32438,90616,1],[56768,52615,1],[47247,2715,0],[96269,56961,1],[27083,76400,1],[8476,4523,1],[16261,75037,0],[98826,4448,1],[42390,67311,1],[71758,26053,1],[24969,16340,1],[15041,90123,1],[96795,13917,0],[37680,14459,1],[12627,4316,1],[46594,91831,1],[88137,22517,0],[50195,59162,0],[61171,90477,0],[93988,71942,0],[18089,43660,1],[68445,94330,1],[97896,19408,1],[49190,45799,0],[42346,85158,0],[12373,23911,0],[36683,61052,0],[26000,14287,1],[10677,84055,0],[37627,92483,0],[84235,81675,0],[65791,14210,0],[94991,62581,0],[55654,77487,1],[20088,35933,0],[33245,48619,0],[29776,61233,0],[62990,33223,0],[51309,81253,0],[71645,93283,0],[58701,65620,1],[65396,77845,1],[80556,61383,1],[51003,19545,0],[18735,10225,1],[95279,15864,0],[56710,88612,1],[36212,83791,0],[67855,40838,1],[8538,98090,1],[96801,14956,0],[42709,66317,1],[68771,40814,0],[37168,89990,0],[3315,38267,1],[97376,65602,1],[85122,12939,0],[16466,51238,1],[33245,27678,1],[99753,56854,1],[99430,168,1],[99463,92843,1],[44135,8827,0],[83701,54391,0],[28816,14841,0],[26145,77903,1],[79947,21498,1],[99018,71669,1],[5460,79976,1],[53675,10088,1],[54093,86389,0],[86564,6323,1],[80842,11917,0],[25995,7080,1],[43874,81064,1],[534,52318,0],[97680,60220,1],[19948,36874,0],[75588,77083,1],[42911,85536,1],[76359,97357,1],[21779,27904,1],[10299,5359,1],[23339,28768,0],[15650,18231,0],[24096,60956,1],[18323,58018,1],[67138,10889,0],[74685,27452,0],[76709,13550,0],[60956,37601,1],[18423,1342,1],[53403,36067,0],[75793,44852,1],[97720,49890,0],[27420,54028,1],[40141,83641,0],[12791,18363,1],[55264,56186,1],[63118,15387,0],[69846,90373,1],[15482,89341,1],[65771,64524,1],[49433,20331,0],[84542,59845,1],[36123,11540,0],[40141,22026,1],[37537,44845,1],[55415,17808,0],[73093,12935,0],[15910,24098,1],[10668,6244,0],[96310,95702,1],[91616,78850,0],[65771,29091,0],[97399,66239,1],[10457,38319,0],[89252,51321,0],[72788,38383,1],[77339,77904,1],[81069,99365,0],[68594,23124,0],[13326,49694,1],[21368,89029,0],[76755,53432,0],[10537,60761,0],[65742,75399,0],[11687,8926,1],[98426,43536,1],[75611,12694,1],[39525,96512,0],[43443,41075,0],[7858,86469,0],[1948,19272,1],[51301,89600,1],[23921,81811,0],[34525,44373,1],[1150,19934,1],[56625,75255,1],[66655,79199,1],[2471,49797,1],[17130,75241,0],[93694,89088,0],[97387,49709,0],[18617,68693,1],[64471,37208,1],[83729,25858,0],[48619,89314,0],[90603,2635,1],[40386,57626,1],[72788,86704,0],[57635,26997,0],[70945,24855,1],[95043,83573,0],[60217,73331,0],[61171,7323,1],[62231,36955,0],[29415,28110,0],[18705,56710,0],[2864,7040,0],[37354,90891,0],[6384,18323,1],[34261,88137,0],[33385,57975,1],[57343,65791,0],[89517,6384,0],[54139,42801,0],[75988,60480,0],[90116,80139,1],[93495,4440,1],[85755,60570,1],[68588,4080,1],[47849,45741,0],[33831,67852,1],[19619,82761,1],[90264,8338,1],[63706,55600,1],[62990,30536,1],[94613,7428,0],[36025,87896,1],[89247,61806,1],[1684,93564,1],[23261,674,0],[77281,34455,0],[21659,59775,1],[18610,18742,0],[65490,36468,0],[29246,84950,1],[18306,56621,1],[3218,85418,0],[70028,83629,0],[3292,13046,1],[14418,18423,1],[83791,22620,0],[93394,63542,1],[78523,31003,1],[21673,90336,1],[70782,10002,0],[76755,73675,1],[78001,42404,1],[68980,83783,1],[36500,62013,1],[16485,19988,1],[49694,3428,0],[66237,35301,0],[2715,58577,1],[89297,66956,1],[29680,56630,0],[39902,85181,1],[98426,33279,0],[5524,71754,0],[32419,67518,1],[58662,91208,1],[3287,34945,0],[68588,15813,0],[44915,14924,1],[66645,88096,1],[77290,50934,1],[5461,25804,1],[40758,83803,1],[40884,20129,1],[22592,80740,0],[90869,37884,0],[47052,81230,0],[17931,37354,0],[43040,57491,0],[92192,22777,1],[50870,73803,0],[55264,58701,0],[13550,43112,0],[94745,12390,1],[54405,6274,1],[44476,71411,0],[80341,9995,1],[72495,82319,0],[78523,85777,0],[42390,48203,0],[72345,80076,1],[76669,35549,0],[73527,89055,0],[30089,44761,0],[43874,1728,0],[27904,19834,0],[80521,24203,1],[39147,74733,1]]

• Passing by Value: Each recursive call creates a new copy of the `unordered_map`, leading to large overhead. For our test cases, this approach took around 2000ms.

Results on passing by value

• Passing by Reference: The `unordered_map` is not copied, and the function operates directly on the original data. This approach drastically reduced the execution time to around 9ms.

Results on passing by reference

Conclusion

In C++, whether you pass arguments by value or by reference can greatly impact your program’s performance and correctness. Always consider the size and complexity of the data structures you’re working with. For large or complex data structures, passing by reference is usually the better choice, as it avoids unnecessary copying and ensures that all changes are reflected in the original data.

By understanding and applying this principle, you can write more efficient and effective C++ code. Happy coding!

This example illustrates the importance of passing by reference for efficiency and correctness, especially in recursive functions working with large data structures. By adopting this approach, you can optimize your code and avoid common pitfalls related to unnecessary data copying.