class Solution {
public:
    long long int getNextStart(long long int curStart, int rowNum, long long int numRows) {
        return 2 * (numRows - 1);
    }
    
    long long int getNext(long long int curStart, int rowNum, long long int numRows) {
        return 2 * (numRows - rowNum - 1);
    }
    
    void writeLine(long long int curStart, int rowNum, string input, string* output, long long int numRows) {
        long long int s_len = input.length();
        if (rowNum == 0 || rowNum == (numRows - 1)) {
            if (curStart < s_len) {
                output->push_back(input[curStart]);
                int delta = getNextStart(curStart, rowNum, numRows);
                if (delta > 0)
                writeLine(curStart + delta, rowNum, input, output, numRows);
            }
        } else {
            if (curStart < s_len) {
                output->push_back(input[curStart]);
                long long int nextInLine = getNext(curStart, rowNum, numRows);
                if (nextInLine < s_len && nextInLine > 0) {
                    output->push_back(input[curStart + nextInLine]);
                }
                int delta = getNextStart(curStart, rowNum, numRows);
                if (delta > 0)
                writeLine(curStart + delta, rowNum, input, output, numRows);
            }
        }
    }
    
    string convert(string s, int numRows) {
        string output;
        for (int i = 0; i < numRows; i++ ) {
            writeLine(i, i, s, &output, numRows);
        }
        cout<<"Zigzag pattern->"<<output<<endl;
        return output;
    }
};