## FranChouChou

FranChouChou is an idol group founded by Kōtarō Tatsumi and led by Saki Nikaidō, consisting of zombies of legendary girls resurrected by Kotaro. Their objective is to save Saga and resurrect the local idol trend in the process.

The idol group’s tentative name was Death Musume, which was later changed to Green Face by Kotaro. The idol members of the group, however, found the names not satisfactory, eventually deciding to rename it to Franchouchou based on the sound Tae made when she sneezed.

The followings are members in the group:

• Zombie #1 Minamoto Sakura
• Zombie #2 Nikaido Saki
• Zombie #3 Mizuno Ai
• Zombie #4 Konno Junko
• Zombie #5 Yugiri
• Zombie #6 Hoshikawa Lily

Now with given a name of an idol, you are asked about her/his number.

### Input

The input contains only single line, one of the names mentioned above.

### Output

You should output the number of the zombie.

### Sample Input

Mizuno Ai


### Sample Output

3


### Solution

#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
getline(cin, s);
cout << map<string, int>{{"Yamada Tae", 0},
{"Minamoto Sakura", 1},
{"Nikaido Saki", 2},
{"Mizuno Ai", 3},
{"Konno Junko", 4},
{"Yugiri", 5},
{"Hoshikawa Lily", 6}}
.at(s);
}


## Number

Reeeeein is good at math problems, because he always holds $n-1$ integers in his brain, and every element exactly appears $k$ times. However, when he once took part in a programming contest, a new integer suddenly squeezed into his brain. This made him so confused that he wrote 5 mistakes within 20 code lines.

### input

The first line contains two integers $n,k$.

The second line contains $n$ integers $a_0,a_1,\dots,a_{n-1}$.

$1<k<n\leq 114514$

$\forall i \in [0,n),a_i \in [0,1919810)$

### output

You should output the number.

### Sample Input

5 2
2 2 3 29 3


### Sample Output

29


### Note

The best algorithm for this problem has a linear time complexity and a constant space complexity. However, solutions with $O(n\log n)$ time complexity will also be accepted!

### Solution

#include <bits/stdc++.h>
using namespace std;
const int BIT = 31;
int n, k, a, b[BIT];
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0, j; i < n; ++i)
for (scanf("%d", &a), j = 0; a; ++j, a >>= 1)
if (a & 1)
++b[j];
for (int j = a = 0; j < BIT; ++j)
a |= b[j] % k << j;
printf("%d", a);
}


## Markdown

Ender starts his blog life today! The first thing for him to learn is markdown, which is a system for annotating a document in a way that is syntactically distinguishable from the text. The user can control the display of the document; formatting words as bold or italic, adding images, and creating lists are just a few of the things one can do with markdown, and the markdown renderer will convert the text to html format.

There are many implementations of markdown renderer. But we only consider a (extremely!) simplified subset here.

• title: Convert # TITLE to <h1>TITLE</h1>, ## TITLE to <h2>TITLE</h2>, $\dots$, ###### TITLE to <h6>TITLE</h6>.
• link: Convert [TEXT](LINK) to <a href="LINK">TEXT</a> tag.
• newline: Put a <br/> tag to the end of a line.

You can simply assume that:

• No extra space at the beginning and end of each line.
• Any character in <> will not appear in the context.
• There is a whitespace between # and TITLE.
• There are no links in title.
• The title always occupies a whole line.
• # will not appear in the context unless it represents a title.
• Any character in []() will not appear in the context unless it is a link.
• []() will not be nested.

If you still have any questions, you can refer to the sample output.

### Input

A markdown style text, only using the rules above.

An empty line represents the end of input, and should be ignored.

The total length of the input will not exceed $10^6$.

### Output

A html format text, each line of input corresponds to each line of output.

You should not output extra whitespaces or emptylines, but a newline at the end of output will be ignored.

### Sample Input

# Welcome
Welcome to [my blog](https://ender-coder.github.io/)!
## H2 title



### Sample Output

<h1>Welcome</h1><br/>
Welcome to <a href="https://ender-coder.github.io/">my blog</a>!<br/>
<h2>H2 title</h2><br/>


### Note

You can output to a “html” file and open it with Web browser.

### Solution

Markdown 渲染器其实有很多实现，大家有空可以继续完善自己的渲染器框架，甚至可以实现一个基于 markdown 的博客引擎（比如用 Ruby 实现的jekyll，用 Node.js 实现的hexo……），相信对代码能力和工程能力都会有比较大的提升。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
char s[N];
int main()
{
for (; fgets(s, N, stdin) && s[0] != '\n'; printf("<br/>\n"))
{
*strchr(s, '\n') = 0;
if (s[0] == '#')
{
int hn = strchr(s, ' ') - s;
printf("<h%d>%s</h%d>", hn, s + hn + 1, hn);
continue;
}
for (int i = 0; s[i]; ++i)
{
if (s[i] != '[')
{
printf("%c", s[i]);
continue;
}
int title = i + 1,
link = strchr(s + title, '(') + 1 - s;
s[link - 2] = s[i = strchr(s + link, ')') - s] = 0;
printf("<a href=\"%s\">%s</a>", s + link, s + title);
}
}
}


## Werewolves

“Werewolves” is a popular card game among young people. In the basic game, there are 2 different groups: the werewolves and the villagers. The purpose of each side is to kill all the opponents, and at least one of themselves survives. During each round of the game, the player will debate players they think are werewolves or not.

Since Emily plays quite well in the Werewolves games, her friends decided to confuse her in the following ways: Like “Player a is a werewolf, or player b is a villager”, the statements they give will contain two pieces of information connected by “or” relationships, of which only one is true.

Now Emily is going to point out all the werewolves, so she wants to know if there’s a situation (even if all of them are werewolves or villagers) that meets the above restrictions.

### Input

The first line contains an integer $N$, indicating the number of players.

Then follows $N$ lines, i-th line contains $4$ string $X,S,Y,T$, indicating the i-th player tells Emily, “Player X is a S or Player Y is a T.”

$1\le N\le 26$

$X,Y\in\lbrace ‘a’,’b’,\dots,’z’\rbrace$

$S,T\in\lbrace “villager”,”werewolf”\rbrace$

### Output

Print a line of lowercase letters denote the werewolves players, separated by white space.

If all players are villagers print “All”.

If there are no situation which obey the rules above, print “Nie” instead.

If there are multiple solutions, any solution will be accepted.

### Sample Input 1

2
a villager a villager
b werewolf b villager


### Sample Output 1

Nie


### Sample Input 2

2
a villager a werewolf
a werewolf b villager


### Sample Output2

All


### Sample Input 3

7
a werewolf f werewolf
a werewolf e werewolf
e werewolf f villager
c villager f werewolf
c villager d villager
d villager f villager
c werewolf c villager


### Sample Output 3

c e f


### Solution

#include <bits/stdc++.h>
using namespace std;
struct Graph
{
struct Vertex
{
vector<int> o;
};
typedef pair<int, int> Edge;
vector<Vertex> v;
vector<Edge> e;
Graph(int n) : v(n) {}
{
v[ed.first].o.push_back(e.size());
e.push_back(ed);
}
};
struct TwoSat : Graph
{
vector<int> ok;
TwoSat(int n) : Graph(n) {}
int dfs(int u, vector<int> &stak)
{
if (ok[u ^ 1])
return 0;
if (ok[u])
return 1;
ok[u] = 1;
stak.push_back(u);
for (int i = 0; i < v[u].o.size(); ++i)
if (!dfs(e[v[u].o[i]].second, stak))
return 0;
return 1;
}
{
ok.assign(v.size(), 0);
for (int i = 0; i < v.size(); i += 2)
if (!ok[i] && !ok[i ^ 1])
{
vector<int> stak;
if (!dfs(i, stak))
{
for (int j = 0; j < stak.size(); ++j)
ok[stak[j]] = 0;
if (!dfs(i ^ 1, stak))
return 0;
}
}
return 1;
}
};
int main()
{
int n;
scanf("%d", &n);
TwoSat g(n << 1);
for (int i = 0; i < n; ++i)
{
char x[9], s[9], y[9], t[9];
scanf("%s%s%s%s", x, s, y, t);
g.addXOR(x[0] - 'a' << 1 | s[0] == 'w', y[0] - 'a' << 1 | t[0] == 'w');
}
return printf("Nie"), 0;
for (int i = n = 0; i < g.ok.size(); i += 2)
if (!g.ok[i])
printf("%c ", 'a' + (i >> 1)), ++n;
if (!n)
printf("All");
}


1. 初始时所有节点为无色。
2. 若当前节点未被染色，染成红色，然后将所有互斥点所在有向子树中的点全部染成黑色。
3. 否则什么都不做，继续处理下一个节点。

#include <bits/stdc++.h>
using namespace std;
struct Graph
{
struct Vertex
{
vector<int> o;
};
typedef pair<int, int> Edge;
vector<Vertex> v;
vector<Edge> e;
Graph(int n) : v(n) {}
{
v[ed.first].o.push_back(e.size());
e.push_back(ed);
}
};
struct StronglyConnectedComponenet : Graph
{
vector<int> dep, sid, stak; //sid=点所属连通块内一点
StronglyConnectedComponenet(int n) : Graph(n) {}
{
dep.assign(v.size(), v.size());
sid.assign(v.size(), v.size());
for (int i = 0; i < v.size(); ++i)
if (dep[i] == v.size())
dfs(i, v.size());
}
int dfs(int u, int fa)
{
int low = dep[u] = fa != v.size() ? dep[fa] + 1 : 0;
stak.push_back(u);
for (int i = 0, k, to; i < v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second, to != fa, 1) //求强连通分量把注释去掉，即允许走回边
{
if (dep[to] == v.size())
low = min(low, dfs(to, u));
else if (sid[to] == v.size())
low = min(low, dep[to]);
}
if (low == dep[u])
for (;;)
{
int x = stak.back();
stak.pop_back();
sid[x] = u;
if (x == u)
break;
}
return low;
}
};
struct TwoSat : StronglyConnectedComponenet
{
vector<int> ok;
TwoSat(int n) : StronglyConnectedComponenet(n) {}
{
for (int i = 0; i < v.size(); i += 2)
if (sid[i] == sid[i ^ 1])
return 0;
vector<vector<int>> g(v.size());
vector<int> ind(v.size(), 0), cf(v.size(), 0), stak;
for (int i = 0; i < v.size(); ++i)
{
cf[sid[i]] = sid[i ^ 1];
for (int j = 0, k; j < v[i].o.size(); ++j)
if (sid[e[k = v[i].o[j]].second] != sid[i])
g[sid[e[k].second]].push_back(sid[i]), ++ind[sid[i]];
}
for (int i = 0; i < v.size(); ++i)
if (sid[i] == i && !ind[i])
stak.push_back(i);
for (ok.assign(v.size(), -1); !stak.empty();)
{
int u = stak.back();
stak.pop_back();
if (ok[u] < 0)
ok[u] = 1, ok[cf[u]] = 0;
for (int i = 0; i < g[u].size(); ++i)
if (!--ind[g[u][i]])
stak.push_back(g[u][i]);
}
for (int i = 0; i < v.size(); ++i)
if (i != sid[i])
ok[i] = ok[sid[i]];
return 1;
}
};
int main()
{
int n;
scanf("%d", &n);
TwoSat g(n << 1);
for (int i = 0; i < n; ++i)
{
char x[9], s[9], y[9], t[9];
scanf("%s%s%s%s", x, s, y, t);
g.addXOR(x[0] - 'a' << 1 | s[0] == 'w', y[0] - 'a' << 1 | t[0] == 'w');
}
return printf("Nie"), 0;
for (int i = n = 0; i < g.ok.size(); i += 2)
if (!g.ok[i])
printf("%c ", 'a' + (i >> 1)), ++n;
if (!n)
printf("All");
}


## TianHe-2A

TianHe-2 has been the fastest supercomputer in the world from June 2013 to June 2016. In September 2017, National Supercomputer Center in Guangzhou announced to upgrade TianHe-2 supercomputing system by the end of the year, replacing the original Intel Xeon Phi accelerator with the domestic accelerator matrix 2000. The upgraded TianHe-2 is called TianHe-2A. The number of nodes has increased from 16000 to 17792, and the floating-point performance has increased from 54.9pflops to 94.97pflops.

During a TianHe-2A’s schedule, the cluster workload manager allocates $n$ computing nodes to users so they can perform work. To simplify this problem, all the $n$ computing nodes are considered to be in a line from left to right and indexed from $0$ to $n-1$. At the beginning each node $i$ holds a nonnegative integer $a_i$. Then the nodes are ready to work, by executing any of the following commands:

• $\text{div}\,l\,r\,w$: $\forall i \in [l,r],a_i\to \lfloor\frac{a_i}{w}\rfloor$
• $\text{sqr}\,l\,r$: $\forall i \in [l,r],a_i\to \lfloor\sqrt{a_i}\rfloor$
• $\text{phi}\,l\,r$: $\forall i \in [l,r],a_i\to \phi(a_i)$
• $\text{ask}\,l\,r$: Ask the max value from $a_l$ to $a_r$.

Now WuK wants you to simulate the operation of Tianhe-2A.

### Input

The first line of the input gives the number of test cases, $t$. $t$ test cases follow.

Each test case starts with a line containing two integers $n,m$, the number of computing nodes and the number of opeartions.

The next line contains $n$ integers $a_0,a_1,\dots,a_{n-1}$.

Then, there are $m$ more lines, each line contains a command as before.

$1<t\leq 20$

$0<n,m,w\leq17792$, and $w$ is an integer

$0\le l\le r<n$

$\forall i \in [0,n),0\le a_i<17792$

### Output

For each $ask$ command, you are asked to output a integer on a new line.

### Sample Input

1
10 10
0 1 2 3 4 5 6 7 8 9
phi 4 4
sqr 5 9
div 0 9 3


### Sample Output

4
2
3
9
2
3
1


### Note

The Euler function $\phi$ is an important kind of function in number theory, $\phi(n)$ represents the amount of the numbers which are smaller than n and coprime to n, and this function has a lot of beautiful characteristics.

Let me put it another way, Euler function $\phi(i)=\sum_{j=1}^{i-1}[\gcd(i,j)=1]$. Moreover, $\phi(0)=0,\phi(1)=1,\phi(2)=1,\phi(3)=2,\phi(4)=2,\dots$

### Solution

#include <bits/stdc++.h>
using namespace std;
const int N = 17792;
struct EulerSieve
{
vector<int> p, m, phi;
EulerSieve(int N) : m(N, 0), phi(N, 0)
{
phi[1] = 1;
for (long long i = 2, k; i < N; ++i)
{
if (!m[i])
p.push_back(m[i] = i), phi[i] = i - 1;
for (int j = 0; j < p.size() && (k = i * p[j]) < N; ++j)
{
phi[k] = phi[i] * p[j];
if ((m[k] = p[j]) == m[i])
break;
phi[k] -= phi[i];
}
}
}
} e(N);
int t, n, m, a[N];
struct SegmentTree
{
int l, r, val;
vector<SegmentTree> ch;
SegmentTree(int l, int r) : l(l), r(r), val(a[l])
{
if (l >= r)
return;
int m = l + (r - l >> 1);
ch = {{l, m}, {m + 1, r}};
val = max(ch[0].val, ch[1].val);
}
void div(int l, int r, int w)
{
if (val < 1 || w == 1)
return;
if (this->l >= this->r)
{
val /= w;
return;
}
if (r <= ch[0].r)
ch[0].div(l, r, w);
else if (l >= ch[1].l)
ch[1].div(l, r, w);
else
ch[0].div(l, ch[0].r, w), ch[1].div(ch[1].l, r, w);
val = max(ch[0].val, ch[1].val);
}
void sqr(int l, int r)
{
if (val < 2)
return;
if (this->l >= this->r)
{
val = sqrt(val);
return;
}
if (r <= ch[0].r)
ch[0].sqr(l, r);
else if (l >= ch[1].l)
ch[1].sqr(l, r);
else
ch[0].sqr(l, ch[0].r), ch[1].sqr(ch[1].l, r);
val = max(ch[0].val, ch[1].val);
}
void phi(int l, int r)
{
if (val < 2)
return;
if (this->l >= this->r)
{
val = e.phi[val];
return;
}
if (r <= ch[0].r)
ch[0].phi(l, r);
else if (l >= ch[1].l)
ch[1].phi(l, r);
else
ch[0].phi(l, ch[0].r), ch[1].phi(ch[1].l, r);
val = max(ch[0].val, ch[1].val);
}
{
if (l <= this->l && this->r <= r)
return val;
if (r <= ch[0].r)
if (l >= ch[1].l)
}
};
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]);
SegmentTree t(0, n - 1);
for (int i = 0, l, r, w; i < m; ++i)
{
char s[9];
scanf("%s%d%d", s, &l, &r);
if (!strcmp(s, "div"))
scanf("%d", &w), t.div(l, r, w);
else if (!strcmp(s, "sqr"))
t.sqr(l, r);
else if (!strcmp(s, "phi"))
t.phi(l, r);
else