#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;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8YXNzZXJ0Lmg+CiNpbmNsdWRlIDxjdGltZT4KI2luY2x1ZGUgPGxpbWl0cy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2xhc3MgU29sdXRpb24KewpwdWJsaWM6CiAgICB2ZWN0b3I8aW50PiBjb25zdHJ1Y3RMYXJnZXN0TnVtYmVyT2YzKGNvbnN0IHZlY3RvcjxpbnQ+ICZhcnIpIHsKICAgICAgICBpbnQgbiA9IGFyci5zaXplKCk7CiAgICAgICAgdmVjdG9yPGludD4gcmVzdWx0OwogICAgICAgIGlmIChuID09IDApIHJldHVybiByZXN1bHQ7CgogICAgICAgIGludCBkaWdpdFN1bSA9IGdldERpZ2l0U3VtKGFycik7CiAgICAgICAgaWYgKGRpZ2l0U3VtICUgMyA9PSAwKSB7CiAgICAgICAgICAgIHJlc3VsdCA9IGFycjsKICAgICAgICAgICAgc29ydChyZXN1bHQuYmVnaW4oKSwgcmVzdWx0LmVuZCgpLCBjdXN0b21pemVkQ21wKTsKICAgICAgICAgICAgcmV0dXJuIHJlc3VsdDsKICAgICAgICB9CgogICAgICAgIGlmIChkaWdpdFN1bSAlIDMgPT0gMSkgewogICAgICAgICAgICBpbnQgbnVtMV8xID0gLTEsIG51bTFfMiA9IC0xOwogICAgICAgICAgICBzZWFyY2hTbWFsbGVzdFdpdGhSZW1haW5kZXIoYXJyLCBudW0xXzEsIG51bTFfMiwgMSk7CiAgICAgICAgICAgIGludCBudW0yXzEgPSAtMSwgbnVtMl8yID0gLTE7CiAgICAgICAgICAgIHNlYXJjaFNtYWxsZXN0V2l0aFJlbWFpbmRlcihhcnIsIG51bTJfMSwgbnVtMl8yLCAyKTsKICAgICAgICAgICAgaWYgKG51bTFfMSA+PSAwICYmIG51bTJfMiA8IDApIHsKICAgICAgICAgICAgICAgIGNvcHlEYXRhV2l0aEV4Y2VwdGlvbihyZXN1bHQsIGFyciwgbnVtMV8xLCAtMSk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSBpZiAobnVtMV8xIDwgMCAmJiBudW0yXzIgPj0gMCkgewogICAgICAgICAgICAgICAgY29weURhdGFXaXRoRXhjZXB0aW9uKHJlc3VsdCwgYXJyLCBudW0yXzEsIG51bTJfMik7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSBpZiAobnVtMV8xID49IDAgJiYgbnVtMl8yID49IDApIHsKICAgICAgICAgICAgICAgIHN0cmluZyByZXMxID0gY29uc3RydWN0TnVtYmVyKDAsIG51bTFfMSk7CiAgICAgICAgICAgICAgICBzdHJpbmcgcmVzMiA9IGNvbnN0cnVjdE51bWJlcihudW0yXzEsIG51bTJfMik7CiAgICAgICAgICAgICAgICBzdHJpbmcgcmVzMyA9IGNvbnN0cnVjdE51bWJlcihudW0yXzIsIG51bTJfMSk7CiAgICAgICAgICAgICAgICBpZiAocmVzMS5zaXplKCkgPiByZXMyLnNpemUoKSAmJiByZXMxLnNpemUoKSA+IHJlczMuc2l6ZSgpKQogICAgICAgICAgICAgICAgICAgIGNvcHlEYXRhV2l0aEV4Y2VwdGlvbihyZXN1bHQsIGFyciwgbnVtMl8xLCBudW0yXzIpOwogICAgICAgICAgICAgICAgZWxzZSBpZiAocmVzMi5zaXplKCkgPiByZXMxLnNpemUoKSB8fCByZXMzLnNpemUoKSA+IHJlczEuc2l6ZSgpKQogICAgICAgICAgICAgICAgICAgIGNvcHlEYXRhV2l0aEV4Y2VwdGlvbihyZXN1bHQsIGFyciwgbnVtMV8xLCAtMSk7CiAgICAgICAgICAgICAgICBlbHNlIGlmIChyZXMxID49IHJlczIgJiYgcmVzMSA+PSByZXMzKQogICAgICAgICAgICAgICAgICAgIGNvcHlEYXRhV2l0aEV4Y2VwdGlvbihyZXN1bHQsIGFyciwgbnVtMl8xLCBudW0yXzIpOwogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIGNvcHlEYXRhV2l0aEV4Y2VwdGlvbihyZXN1bHQsIGFyciwgbnVtMV8xLCAtMSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgZWxzZSB7CiAgICAgICAgICAgIGludCBudW0xXzEgPSAtMSwgbnVtMV8yID0gLTE7CiAgICAgICAgICAgIHNlYXJjaFNtYWxsZXN0V2l0aFJlbWFpbmRlcihhcnIsIG51bTFfMSwgbnVtMV8yLCAxKTsKICAgICAgICAgICAgaW50IG51bTJfMSA9IC0xLCBudW0yXzIgPSAtMTsKICAgICAgICAgICAgc2VhcmNoU21hbGxlc3RXaXRoUmVtYWluZGVyKGFyciwgbnVtMl8xLCBudW0yXzIsIDIpOwogICAgICAgICAgICBpZiAobnVtMl8xID49IDAgJiYgbnVtMV8yIDwgMCkgewogICAgICAgICAgICAgICAgY29weURhdGFXaXRoRXhjZXB0aW9uKHJlc3VsdCwgYXJyLCBudW0yXzEsIC0xKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIGlmIChudW0yXzEgPCAwICYmIG51bTFfMiA+PSAwKSB7CiAgICAgICAgICAgICAgICBjb3B5RGF0YVdpdGhFeGNlcHRpb24ocmVzdWx0LCBhcnIsIG51bTFfMSwgbnVtMV8yKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIGlmIChudW0yXzEgPj0gMCAmJiBudW0xXzIgPj0gMCkgewogICAgICAgICAgICAgICAgc3RyaW5nIHJlczEgPSBjb25zdHJ1Y3ROdW1iZXIoMCwgbnVtMl8xKTsKICAgICAgICAgICAgICAgIHN0cmluZyByZXMyID0gY29uc3RydWN0TnVtYmVyKG51bTFfMSwgbnVtMV8yKTsKICAgICAgICAgICAgICAgIHN0cmluZyByZXMzID0gY29uc3RydWN0TnVtYmVyKG51bTFfMiwgbnVtMV8xKTsKICAgICAgICAgICAgICAgIGlmIChyZXMxLnNpemUoKSA+IHJlczIuc2l6ZSgpICYmIHJlczEuc2l6ZSgpID4gcmVzMy5zaXplKCkpCiAgICAgICAgICAgICAgICAgICAgY29weURhdGFXaXRoRXhjZXB0aW9uKHJlc3VsdCwgYXJyLCBudW0xXzEsIG51bTFfMik7CiAgICAgICAgICAgICAgICBlbHNlIGlmIChyZXMyLnNpemUoKSA+IHJlczEuc2l6ZSgpIHx8IHJlczMuc2l6ZSgpID4gcmVzMS5zaXplKCkpCiAgICAgICAgICAgICAgICAgICAgY29weURhdGFXaXRoRXhjZXB0aW9uKHJlc3VsdCwgYXJyLCBudW0yXzEsIC0xKTsKICAgICAgICAgICAgICAgIGVsc2UgaWYgKHJlczEgPj0gcmVzMiAmJiByZXMxID49IHJlczMpCiAgICAgICAgICAgICAgICAgICAgY29weURhdGFXaXRoRXhjZXB0aW9uKHJlc3VsdCwgYXJyLCBudW0xXzEsIG51bTFfMik7CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgY29weURhdGFXaXRoRXhjZXB0aW9uKHJlc3VsdCwgYXJyLCBudW0yXzEsIC0xKTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgc29ydChyZXN1bHQuYmVnaW4oKSwgcmVzdWx0LmVuZCgpLCBjdXN0b21pemVkQ21wKTsKICAgICAgICByZXR1cm4gcmVzdWx0OwogICAgfQoKcHJpdmF0ZToKICAgIGludCBnZXREaWdpdFN1bShpbnQgbikgewogICAgICAgIGludCBzdW0gPSAwOwogICAgICAgIGludCByID0gMDsKICAgICAgICB3aGlsZSAobikgewogICAgICAgICAgICByID0gbiAlIDEwOwogICAgICAgICAgICBuIC89IDEwOwogICAgICAgICAgICBzdW0gKz0gcjsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHN1bTsKICAgIH0KCiAgICB2b2lkIHNlYXJjaFNtYWxsZXN0V2l0aFJlbWFpbmRlcihjb25zdCB2ZWN0b3I8aW50PiAmYXJyLCBpbnQgJnJlczEsIGludCAmcmVzMiwgaW50IHRhcmdldF9yKSB7CiAgICAgICAgaW50IG4gPSBhcnIuc2l6ZSgpOwogICAgICAgIHJlczEgPSByZXMyID0gSU5UX01BWDsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkgewogICAgICAgICAgICBpZiAoYXJyW2ldICUgMyAhPSB0YXJnZXRfcikgY29udGludWU7CgogICAgICAgICAgICBpZiAoYXJyW2ldIDwgcmVzMSkgewogICAgICAgICAgICAgICAgcmVzMiA9IHJlczE7CiAgICAgICAgICAgICAgICByZXMxID0gYXJyW2ldOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgaWYgKGFycltpXSA8IHJlczIpCiAgICAgICAgICAgICAgICByZXMyID0gYXJyW2ldOwogICAgICAgIH0KCiAgICAgICAgaWYgKHJlczEgPT0gSU5UX01BWCkgcmVzMSA9IC0xOwogICAgICAgIGlmIChyZXMyID09IElOVF9NQVgpIHJlczIgPSAtMTsgICAgCiAgICB9CgogICAgdm9pZCBjb3B5RGF0YVdpdGhFeGNlcHRpb24odmVjdG9yPGludD4gJmRlc3QsIGNvbnN0IHZlY3RvcjxpbnQ+ICZzcmMsIGludCB0MSwgaW50IHQyKSB7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBzcmMuc2l6ZSgpOyArK2kpIHsKICAgICAgICAgICAgaWYgKHNyY1tpXSA9PSB0MSkKICAgICAgICAgICAgICAgIHQxID0gLTE7CiAgICAgICAgICAgIGVsc2UgaWYgKHNyY1tpXSA9PSB0MikKICAgICAgICAgICAgICAgIHQyID0gLTE7CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIGRlc3QucHVzaF9iYWNrKHNyY1tpXSk7CiAgICAgICAgfSAgICAKICAgIH0KCiAgICBzdGF0aWMgc3RyaW5nIGNvbnN0cnVjdE51bWJlcihpbnQgbjEsIGludCBuMikgewogICAgICAgIGlmIChuMSA9PSAwICYmIG4yID09IDApIHJldHVybiAiMCI7CiAgICAgICAgaW50IHIgPSAwOwogICAgICAgIHN0cmluZyByZXN1bHQ7CiAgICAgICAgd2hpbGUgKG4xKSB7CiAgICAgICAgICAgIHIgPSBuMSAlIDEwOwogICAgICAgICAgICBuMSAvPSAxMDsKICAgICAgICAgICAgcmVzdWx0ICs9ICcwJyArIHI7CiAgICAgICAgfQoKICAgICAgICBpbnQgc3RhcnQgPSAwLCBlbmQgPSByZXN1bHQuc2l6ZSgpIC0gMTsKICAgICAgICB3aGlsZSAoc3RhcnQgPCBlbmQpCiAgICAgICAgICAgIHN3YXAocmVzdWx0W3N0YXJ0KytdLCByZXN1bHRbZW5kLS1dKTsKCiAgICAgICAgc3RhcnQgPSByZXN1bHQuc2l6ZSgpOwogICAgICAgIHdoaWxlIChuMikgewogICAgICAgICAgICByID0gbjIgJSAxMDsKICAgICAgICAgICAgbjIgLz0gMTA7CiAgICAgICAgICAgIHJlc3VsdCArPSAnMCcgKyByOwogICAgICAgIH0KCiAgICAgICAgZW5kID0gcmVzdWx0LnNpemUoKSAtIDE7CiAgICAgICAgd2hpbGUgKHN0YXJ0IDwgZW5kKQogICAgICAgICAgICBzd2FwKHJlc3VsdFtzdGFydCsrXSwgcmVzdWx0W2VuZC0tXSk7CiAgICAgICAgcmV0dXJuIHJlc3VsdDsgICAgCiAgICB9CgogICAgc3RhdGljIGJvb2wgY3VzdG9taXplZENtcChjb25zdCBpbnQgJm4xLCBjb25zdCBpbnQgJm4yKSB7CiAgICAgICAgc3RyaW5nIHJlczEgPSBjb25zdHJ1Y3ROdW1iZXIobjEsIG4yKTsKICAgICAgICBzdHJpbmcgcmVzMiA9IGNvbnN0cnVjdE51bWJlcihuMiwgbjEpOwogICAgICAgIGlmIChyZXMxLnNpemUoKSA+IHJlczIuc2l6ZSgpKSByZXR1cm4gdHJ1ZTsKICAgICAgICBpZiAocmVzMi5zaXplKCkgPiByZXMxLnNpemUoKSkgcmV0dXJuIGZhbHNlOwogICAgICAgIHJldHVybiByZXMxID4gcmVzMjsKICAgIH0KCnB1YmxpYzoKICAgIGludCBnZXREaWdpdFN1bShjb25zdCB2ZWN0b3I8aW50PiAmYXJyKSB7CiAgICAgICAgaW50IHN1bSA9IDA7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBhcnIuc2l6ZSgpOyArK2kpCiAgICAgICAgICAgIHN1bSArPSBnZXREaWdpdFN1bShhcnJbaV0pOwogICAgICAgIHJldHVybiBzdW07CiAgICB9Cn07Cgp2b2lkIE91dHB1dChjb25zdCB2ZWN0b3I8aW50PiAmYXJyKSB7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IGFyci5zaXplKCk7ICsraSkKICAgICAgICBjb3V0IDw8IGFycltpXSA8PCAiICI7CiAgICBjb3V0IDw8IGVuZGw7Cn0KCnZvaWQgR2VuZXJhdGVBcnJheSh2ZWN0b3I8aW50PiAmYXJyLCBpbnQgbiwgaW50IE1BWF9WQUwpIHsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKQogICAgICAgIGFyci5wdXNoX2JhY2socmFuZCgpICUgTUFYX1ZBTCArIDEpOwp9CgppbnQgbWFpbigpCnsKICAgIGNvbnN0IGludCBNQVhfTlVNID0gNjAwOwogICAgY29uc3QgaW50IE1BWF9UUlkgPSAzMDsKICAgIGNvbnN0IGludCBNQVhfQVJSX1NJWkUgPSAzMDsKICAgIHZlY3RvcjxpbnQ+IHNyY0FycjsKICAgIFNvbHV0aW9uIHNvOwogICAgdmVjdG9yPGludD4gcmVzdWx0OwogICAgaW50IHRyeVRpbWVzID0gTUFYX1RSWTsKCiAgICBzcmFuZCh0aW1lKE5VTEwpKTsKCiAgICB3aGlsZSAodHJ5VGltZXMtLSA+IDApIHsKICAgICAgICBzcmNBcnIuY2xlYXIoKTsKICAgICAgICBHZW5lcmF0ZUFycmF5KHNyY0FyciwgcmFuZCgpICUgTUFYX0FSUl9TSVpFICsgMSwgTUFYX05VTSk7CiAgICAgICAgcmVzdWx0ID0gc28uY29uc3RydWN0TGFyZ2VzdE51bWJlck9mMyhzcmNBcnIpOwogICAgICAgIGFzc2VydChzby5nZXREaWdpdFN1bShyZXN1bHQpICUgMyA9PSAwKTsKCiAgICAgICAgY291dCA8PCAiT3JpZ2luYWwgQXJyYXkgaXM6IiA8PCBlbmRsOwogICAgICAgIE91dHB1dChzcmNBcnIpOwogICAgICAgIGNvdXQgPDwgIkNvbnN0cnVjdGVkIE1heGltdW0gTnVtYmVyIHRoYXQgaXMgbXVsdGlwbGUgb2YgMyBpczoiIDw8IGVuZGw7CiAgICAgICAgT3V0cHV0KHJlc3VsdCk7CiAgICAgICAgY291dCA8PCAiLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSIgPDwgZW5kbDsgICAgCiAgICB9CgoJcmV0dXJuIDA7Cn0=