奶牛 Bessie 最近在学习字符串操作，它用如下的规则逐一的构造出新的字符串：

Question

喵喵字符串
描述

贡菊最近在学习字符串操作，它用如下的规则逐一的构造出新的字符串：

S(0)=mew

S(1)=S(0)+me+ww+S(0)=mew+me+ww+mew=mewmewwmew

S(2)=S(1)+me+www+S(1)=mewmwwmew+me+www+mewmewwmew=mewmewwmewmewwwmewmewwmew

……

贡菊通过这个规律产生字符串，直到最后产生的那个字符串长度不小于读入的整数 n 才停止。

请问第 n 个字母是什么？

输入
一个整数 n (1≤n≤100)

输出
第 n 个字母

输入样例 1

11
输出样例 1

m
求解不用递推

Answer 1

给出一种比较高效的解法：

#include <iostream>
#include <string>
using namespace std;

int main()
{
    int n;
    cin >> n;
    string s = "mew";
    for(int i=1; ; i++)
    {
        if(s.length() >= n)
        {
            cout << s[n - 1] << endl;
            return 0;
        }
        s = s + "me" + string(i + 1, 'w') + s;
    }
    return 0;
}

n = 100 时，输出 w，运行时间 17ms。