A. Eleven

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Eleven wants to choose a new name for herself. As a bunch of geeks, her friends suggested an algorithm to choose a name for her. Eleven wants her name to have exactly n characters.

Her friend suggested that her name should only consist of uppercase and lowercase letters 'O'. More precisely, they suggested that the i-th letter of her name should be 'O' (uppercase) if i is a member of Fibonacci sequence, and 'o' (lowercase) otherwise. The letters in the name are numbered from 1 to n. Fibonacci sequence is the sequence f where

• f1 = 1,
• f2 = 1,
• fn = fn - 2 + fn - 1 (n > 2).

As her friends are too young to know what Fibonacci sequence is, they asked you to help Eleven determine her new name.

Input

The first and only line of input contains an integer n (1 ≤ n ≤ 1000).

Output

Print Eleven's new name on the first and only line of output.

Examples

input

8

output

OOOoOooO

input

15

output

OOOoOooOooooOoo

 

 是菲波那切数列的数输出O，否则输出o，只要15项就行了（脑残了把房间的那个hack

#include
        
         using namespace std;int a[1005],f[100],n;int main(){    f[1]=1,f[0]=1;    for(int i=1;f[i]<=1005;i++)        f[i+1]=f[i]+f[i-1],a[f[i]]=1;    cin>>n;    for(int i=1;i<=n;i++)        if(a[i]==1)cout<<"O";        else cout<<"o";    return 0;}
        

B. Radio Station

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

As the guys fried the radio station facilities, the school principal gave them tasks as a punishment. Dustin's task was to add comments to nginx configuration for school's website. The school has n servers. Each server has a name and an ip (names aren't necessarily unique, but ips are). Dustin knows the ip and name of each server. For simplicity, we'll assume that an nginx command is of form "command ip;" where command is a string consisting of English lowercase letter only, and ip is the ip of one of school servers.

Each ip is of form "a.b.c.d" where a, b, c and d are non-negative integers less than or equal to 255 (with no leading zeros). The nginx configuration file Dustin has to add comments to has m commands. Nobody ever memorizes the ips of servers, so to understand the configuration better, Dustin has to comment the name of server that the ip belongs to at the end of each line (after each command). More formally, if a line is "command ip;" Dustin has to replace it with "command ip; #name" where name is the name of the server with ip equal to ip.

Dustin doesn't know anything about nginx, so he panicked again and his friends asked you to do his task for him.

Input

The first line of input contains two integers n and m (1 ≤ n, m ≤ 1000).

The next n lines contain the names and ips of the servers. Each line contains a string name, name of the server and a string ip, ip of the server, separated by space (1 ≤ |name| ≤ 10, name only consists of English lowercase letters). It is guaranteed that all ip are distinct.

The next m lines contain the commands in the configuration file. Each line is of form "command ip;" (1 ≤ |command| ≤ 10, commandonly consists of English lowercase letters). It is guaranteed that ip belongs to one of the n school servers.

Output

Print m lines, the commands in the configuration file after Dustin did his task.

Examples

input

2 2 main 192.168.0.2 replica 192.168.0.1 block 192.168.0.1; proxy 192.168.0.2;

output

block 192.168.0.1; #replica proxy 192.168.0.2; #main

input

3 5 google 8.8.8.8 codeforces 212.193.33.27 server 138.197.64.57 redirect 138.197.64.57; block 8.8.8.8; cf 212.193.33.27; unblock 8.8.8.8; check 138.197.64.57;

output

redirect 138.197.64.57; #server block 8.8.8.8; #google cf 212.193.33.27; #codeforces unblock 8.8.8.8; #google check 138.197.64.57; #server

 

 

一对一的，一个IP对应一个服务器，所以直接map就行了（脑残了想的有点多

---

#include
          
           using namespace std;int main(){    int n,m;    cin>>n>>m;    map
           
            M;    string s,c;    for(int i=0;i
            
             >s>>c;        M[c]=s;    }    for(int i=0;i
             
              >s>>c;        cout<
              <<" "<
               
                <<" #"<
                
                 <<"\n"; } return 0;}
                
               
             
            
           
          

C. The Monster

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

As Will is stuck in the Upside Down, he can still communicate with his mom, Joyce, through the Christmas lights (he can turn them on and off with his mind). He can't directly tell his mom where he is, because the monster that took him to the Upside Down will know and relocate him.

Thus, he came up with a puzzle to tell his mom his coordinates. His coordinates are the answer to the following problem.

A string consisting only of parentheses ('(' and ')') is called a bracket sequence. Some bracket sequence are called correct bracket sequences. More formally:

• Empty string is a correct bracket sequence.
• if s is a correct bracket sequence, then (s) is also a correct bracket sequence.
• if s and t are correct bracket sequences, then st (concatenation of s and t) is also a correct bracket sequence.

A string consisting of parentheses and question marks ('?') is called pretty if and only if there's a way to replace each question mark with either '(' or ')' such that the resulting string is a non-empty correct bracket sequence.

Will gave his mom a string s consisting of parentheses and question marks (using Morse code through the lights) and his coordinates are the number of pairs of integers (l, r) such that 1 ≤ l ≤ r ≤ |s| and the string slsl + 1... sr is pretty, where si is i-th character of s.

Joyce doesn't know anything about bracket sequences, so she asked for your help.

Input

The first and only line of input contains string s, consisting only of characters '(', ')' and '?' (2 ≤ |s| ≤ 5000).

Output

Print the answer to Will's puzzle in the first and only line of output.

Examples

input

((?))

output

4

input

??()??

output

7

Note

For the first sample testcase, the pretty substrings of s are:

1. "(?" which can be transformed to "()".
2. "?)" which can be transformed to "()".
3. "((?)" which can be transformed to "(())".
4. "(?))" which can be transformed to "(())".

For the second sample testcase, the pretty substrings of s are:

1. "??" which can be transformed to "()".
2. "()".
3. "??()" which can be transformed to "()()".
4. "?()?" which can be transformed to "(())".
5. "??" which can be transformed to "()".
6. "()??" which can be transformed to "()()".
7. "??()??" which can be transformed to "()()()".

 

？可以填()，然后判断这个括号序列是不是合法

死活出不了，因为自己没有想到这个贪心，我也想到了要去判断每个序列是不是合法

左括号是不能限制序列的，又括号的好就不能出现多余的了，但是？能代替左右，假设其代替左，那么l小于0的时候，就要把?变了，如果不合法的话，r不合法就检查下一序列了，其他的继续

非常巧妙

#include
            
             using namespace std;int main(){    string s;    cin>>s;    int ans=0;    for(int i=0;s[i];i++)    {        int l=0,r=0;        for(int j=i;s[j];j++)        {            if(s[j]=='(')l++,r++;            else if(s[j]==')')l--,r--;            else l--,r++;            if(l<0)l+=2;            if(r<0)break;            if(!l)ans++;        }    }    cout<
            

 

D. MADMAX

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

As we all know, Max is the best video game player among her friends. Her friends were so jealous of hers, that they created an actual game just to prove that she's not the best at games. The game is played on a directed acyclic graph (a DAG) with n vertices and m edges. There's a character written on each edge, a lowercase English letter.

Max and Lucas are playing the game. Max goes first, then Lucas, then Max again and so on. Each player has a marble, initially located at some vertex. Each player in his/her turn should move his/her marble along some edge (a player can move the marble from vertex v to vertex u if there's an outgoing edge from v to u). If the player moves his/her marble from vertex v to vertex u, the "character" of that round is the character written on the edge from v to u. There's one additional rule; the ASCII code of character of round i should be greater than or equal to the ASCII code of character of round i - 1 (for i > 1). The rounds are numbered for both players together, i. e. Max goes in odd numbers, Lucas goes in even numbers. The player that can't make a move loses the game. The marbles may be at the same vertex at the same time.

Since the game could take a while and Lucas and Max have to focus on finding Dart, they don't have time to play. So they asked you, if they both play optimally, who wins the game?

You have to determine the winner of the game for all initial positions of the marbles.

Input

The first line of input contains two integers n and m (2 ≤ n ≤ 100, ).

The next m lines contain the edges. Each line contains two integers v, u and a lowercase English letter c, meaning there's an edge from vto u written c on it (1 ≤ v, u ≤ n, v ≠ u). There's at most one edge between any pair of vertices. It is guaranteed that the graph is acyclic.

Output

Print n lines, a string of length n in each one. The j-th character in i-th line should be 'A' if Max will win the game in case her marble is initially at vertex i and Lucas's marble is initially at vertex j, and 'B' otherwise.

Examples

input

4 4 1 2 b 1 3 a 2 4 c 3 4 b

output

BAAA ABAA BBBA BBBB

input

5 8 5 3 h 1 2 c 3 1 c 3 2 r 5 1 r 4 3 z 5 4 r 5 2 h

output

BABBB BBBBB AABBB AAABA AAAAB

Note

Here's the graph in the first sample test case:

Here's the graph in the second sample test case:

 

 

它是一个DAG，所以直接记忆化搜索就行了，我太蠢了

#include
          
           using namespace std;const int N=105;int SG[105][105][26];int head[5005],nxt[5005],to[5005],f[5005];int tot;int DFS(int i,int j,int k){    if(SG[i][j][k])return SG[i][j][k];    for(int p=head[i]; p; p=nxt[p])        if(f[p]>=k&&!DFS(j,to[p],f[p]))SG[i][j][k]=1;    return SG[i][j][k];}void add(int u,int v,int w){    nxt[++tot]=head[u],head[u]=tot,to[tot]=v,f[tot]=w;}int main(){    int n,m;    char c;    cin>>n>>m;    for(int i=1,u,v; i<=m; i++)cin>>u>>v>>c,add(u,v,c-'a');    for(int i=1; i<=n; i++)    {        for(int j=1; j<=n; j++)            if(DFS(i,j,0))cout<<'A';            else cout <<'B';        cout<<"\n";    }    return 0;}