/* Author: Nguyen Chi Thanh - High School for the Gifted - VNU.HCM (i2528) */ #include <bits/stdc++.h> using namespace std; // #define int long long #define ull unsigned long long #define ld long double #define pii pair<int, int> #define fi first #define se second #define __builtin_popcount __builtin_popcountll #define all(x) (x).begin(), (x).end() #define BIT(x, i) (((x) >> (i)) & 1) #define MASK(x) ((1ll << (x))) #define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n'; const int MAXN = 2e6 + 5; int numNodes, n; int type[MAXN]; // ?: 0, max: -1, min = 1 int par[MAXN]; vector<int> adj[MAXN]; void init() { string s; cin >> s; n = count(all(s), '?'); // Build binary tree from the expression int ptr = 0; numNodes = 0; vector<int> st; // Stack-based vector st.push_back(0); // Virtual node while (ptr < (int)s.size()) { if (s[ptr] == '?') { numNodes++; type[numNodes] = 0; par[numNodes] = st.back(); ++ptr; continue; } if (s[ptr] == 'm') { char c = s[ptr + 1]; // max or min ++numNodes; type[numNodes] = (c == 'a' ? -1 : 1); par[numNodes] = st.back(); st.push_back(numNodes); ptr += 4; continue; } if (s[ptr] == ')') { assert(!st.empty()); // For safe ++ptr; st.pop_back(); continue; } if (s[ptr] == ',') {++ptr; continue;} } for (int i = 1; i <= numNodes; ++i) { if (par[i]) { adj[i].push_back(par[i]); adj[par[i]].push_back(i); } } } namespace subtask1 { bool check() {return n <= 9;} int curQues = 0; vector<int> val, perm; void dfs(int u, int par = 0) { if ((int)adj[u].size() == 1) { val[u] = perm[curQues]; curQues++; return; } val[u] = -1; for (int v : adj[u]) { if (v == par) continue; dfs(v, u); if (val[u] == -1) val[u] = val[v]; else { if (type[u] == -1) val[u] = max(val[u], val[v]); else if (type[u] == 1) val[u] = min(val[u], val[v]); } } } void solve() { val.resize(numNodes + 5, 0); perm.resize(n); iota(all(perm), 1); set<int> res; do { curQues = 0; dfs(1); res.insert(val[1]); } while (next_permutation(all(perm))); cout << (int)res.size(); cout << '\n'; for (auto v : res) cout << v << ' '; } } namespace full { vector<pii> dp; vector<int> sz; vector<int> children; void dfs(int u, int par = -1) { if ((int)adj[u].size() == 1) { dp[u] = {1, 1}; sz[u] = 1; return; } children.clear(); for (int v : adj[u]) if (v != par) children.push_back(v); int left = children[0], right = children[1]; dfs(left, u); dfs(right, u); sz[u] = sz[left] + sz[right]; if (type[u] == 1) { dp[u].fi = min(dp[left].fi, dp[right].fi); dp[u].se = dp[left].se + dp[right].se - 1; } else { dp[u].fi = dp[left].fi + dp[right].fi; dp[u].se = max(dp[left].se + sz[right], sz[left] + dp[right].se); } // cout << u << ' ' << dp[u].fi << ' ' << dp[u].se << '\n'; } void solve() { dp.resize(numNodes + 5); sz.resize(numNodes + 5); dfs(1); cout << dp[1].se - dp[1].fi + 1; } } signed main() { #ifdef NCTHANH freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); init(); // if (subtask1::check()) return subtask1::solve(), 0; full::solve(); return 0; }