#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <assert.h>
#include <ctime>
#include <limits.h>
using namespace std;

class Solution
{
public:
    vector<int> constructLargestNumberOf3(const vector<int> &arr) {
        int n = arr.size();
        vector<int> result;
        if (n == 0) return result;

        int digitSum = getDigitSum(arr);
        if (digitSum % 3 == 0) {
            result = arr;
            sort(result.begin(), result.end(), customizedCmp);
            return result;
        }

        if (digitSum % 3 == 1) {
            int num1_1 = -1, num1_2 = -1;
            searchSmallestWithRemainder(arr, num1_1, num1_2, 1);
            int num2_1 = -1, num2_2 = -1;
            searchSmallestWithRemainder(arr, num2_1, num2_2, 2);
            if (num1_1 >= 0 && num2_2 < 0) {
                copyDataWithException(result, arr, num1_1, -1);
            }
            else if (num1_1 < 0 && num2_2 >= 0) {
                copyDataWithException(result, arr, num2_1, num2_2);
            }
            else if (num1_1 >= 0 && num2_2 >= 0) {
                string res1 = constructNumber(0, num1_1);
                string res2 = constructNumber(num2_1, num2_2);
                string res3 = constructNumber(num2_2, num2_1);
                if (res1.size() > res2.size() && res1.size() > res3.size())
                    copyDataWithException(result, arr, num2_1, num2_2);
                else if (res2.size() > res1.size() || res3.size() > res1.size())
                    copyDataWithException(result, arr, num1_1, -1);
                else if (res1 >= res2 && res1 >= res3)
                    copyDataWithException(result, arr, num2_1, num2_2);
                else
                    copyDataWithException(result, arr, num1_1, -1);
            }
        }
        else {
            int num1_1 = -1, num1_2 = -1;
            searchSmallestWithRemainder(arr, num1_1, num1_2, 1);
            int num2_1 = -1, num2_2 = -1;
            searchSmallestWithRemainder(arr, num2_1, num2_2, 2);
            if (num2_1 >= 0 && num1_2 < 0) {
                copyDataWithException(result, arr, num2_1, -1);
            }
            else if (num2_1 < 0 && num1_2 >= 0) {
                copyDataWithException(result, arr, num1_1, num1_2);
            }
            else if (num2_1 >= 0 && num1_2 >= 0) {
                string res1 = constructNumber(0, num2_1);
                string res2 = constructNumber(num1_1, num1_2);
                string res3 = constructNumber(num1_2, num1_1);
                if (res1.size() > res2.size() && res1.size() > res3.size())
                    copyDataWithException(result, arr, num1_1, num1_2);
                else if (res2.size() > res1.size() || res3.size() > res1.size())
                    copyDataWithException(result, arr, num2_1, -1);
                else if (res1 >= res2 && res1 >= res3)
                    copyDataWithException(result, arr, num1_1, num1_2);
                else
                    copyDataWithException(result, arr, num2_1, -1);
            }
        }

        sort(result.begin(), result.end(), customizedCmp);
        return result;
    }

private:
    int getDigitSum(int n) {
        int sum = 0;
        int r = 0;
        while (n) {
            r = n % 10;
            n /= 10;
            sum += r;
        }
        return sum;
    }

    void searchSmallestWithRemainder(const vector<int> &arr, int &res1, int &res2, int target_r) {
        int n = arr.size();
        res1 = res2 = INT_MAX;
        for (int i = 0; i < n; ++i) {
            if (arr[i] % 3 != target_r) continue;

            if (arr[i] < res1) {
                res2 = res1;
                res1 = arr[i];
            }
            else if (arr[i] < res2)
                res2 = arr[i];
        }

        if (res1 == INT_MAX) res1 = -1;
        if (res2 == INT_MAX) res2 = -1;    
    }

    void copyDataWithException(vector<int> &dest, const vector<int> &src, int t1, int t2) {
        for (int i = 0; i < src.size(); ++i) {
            if (src[i] == t1)
                t1 = -1;
            else if (src[i] == t2)
                t2 = -1;
            else
                dest.push_back(src[i]);
        }    
    }

    static string constructNumber(int n1, int n2) {
        if (n1 == 0 && n2 == 0) return "0";
        int r = 0;
        string result;
        while (n1) {
            r = n1 % 10;
            n1 /= 10;
            result += '0' + r;
        }

        int start = 0, end = result.size() - 1;
        while (start < end)
            swap(result[start++], result[end--]);

        start = result.size();
        while (n2) {
            r = n2 % 10;
            n2 /= 10;
            result += '0' + r;
        }

        end = result.size() - 1;
        while (start < end)
            swap(result[start++], result[end--]);
        return result;    
    }

    static bool customizedCmp(const int &n1, const int &n2) {
        string res1 = constructNumber(n1, n2);
        string res2 = constructNumber(n2, n1);
        if (res1.size() > res2.size()) return true;
        if (res2.size() > res1.size()) return false;
        return res1 > res2;
    }

public:
    int getDigitSum(const vector<int> &arr) {
        int sum = 0;
        for (int i = 0; i < arr.size(); ++i)
            sum += getDigitSum(arr[i]);
        return sum;
    }
};

void Output(const vector<int> &arr) {
    for (int i = 0; i < arr.size(); ++i)
        cout << arr[i] << " ";
    cout << endl;
}

void GenerateArray(vector<int> &arr, int n, int MAX_VAL) {
    for (int i = 0; i < n; ++i)
        arr.push_back(rand() % MAX_VAL + 1);
}

int main()
{
    const int MAX_NUM = 600;
    const int MAX_TRY = 30;
    const int MAX_ARR_SIZE = 30;
    vector<int> srcArr;
    Solution so;
    vector<int> result;
    int tryTimes = MAX_TRY;

    srand(time(NULL));

    while (tryTimes-- > 0) {
        srcArr.clear();
        GenerateArray(srcArr, rand() % MAX_ARR_SIZE + 1, MAX_NUM);
        result = so.constructLargestNumberOf3(srcArr);
        assert(so.getDigitSum(result) % 3 == 0);

        cout << "Original Array is:" << endl;
        Output(srcArr);
        cout << "Constructed Maximum Number that is multiple of 3 is:" << endl;
        Output(result);
        cout << "-------------------------------------------" << endl;    
    }

	return 0;
}