Vasya And Password（CodeForces

Vasya came up with a password to register for EatForces — a string $s$

But since EatForces takes care of the security of its users, user passwords must contain at least one digit, at least one uppercase Latin letter and at least one lowercase Latin letter. For example, the passwords "abaCABA12", "Z7q" and "3R24m" are valid, and the passwords "qwerty", "qwerty12345" and "Password" are not.

A substring of string $s$

Vasya's password, however, may come too weak for the security settings of EatForces. He likes his password, so he wants to replace some its substring with another string of the same length in order to satisfy the above conditions. This operation should be performed exactly once, and the chosen string should have the minimal possible length.

Note that the length of $s$

Input

The first line contains a single integer $T$

Each of the next $T$

Only $T = 1$

Output

For each testcase print a renewed password, which corresponds to given conditions.

The length of the replaced substring is calculated as following: write down all the changed positions. If there are none, then the length is $0$

It is guaranteed that such a password always exists.

If there are several suitable passwords — output any of them.

Example

Input

2
abcDCE
htQw27

Output

abcD4E
htQw27

Note

In the first example Vasya's password lacks a digit, he replaces substring "C" with "4" and gets password "abcD4E". That means, he changed the substring of length 1.

In the second example Vasya's password is ok from the beginning, and nothing has to be changed. That is the same as replacing the empty substring with another empty substring (length 0).

题解：虽然是A类题，但是还是没能一遍过（哭.....，代码比较low，写给自己体会。

代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<string>
 6 #include<cmath>
 7 #include<map>
 8 #include<stack>
 9 #include<vector>
10 #include<queue>
11 #include<set>
12 #include<algorithm>
13 #define max(a,b)   (a>b?a:b)
14 #define min(a,b)   (a<b?a:b)
15 #define swap(a,b)  (a=a+b,b=a-b,a=a-b)
16 #define maxn 320007
17 #define N 100000000
18 #define INF 0x3f3f3f3f
19 #define mod 1000000009
20 #define e  2.718281828459045
21 #define eps 1.0e18
22 #define PI acos(-1)
23 #define lowbit(x) (x&(-x))
24 #define read(x) scanf("%d",&x)
25 #define put(x) printf("%d
",x)
26 #define memset(x,y) memset(x,y,sizeof(x))
27 #define Debug(x) cout<<x<<" "<<endl
28 #define lson i << 1,l,m
29 #define rson i << 1 | 1,m + 1,r
30 #define ll long long
31 //std::ios::sync_with_stdio(false);
32 //cin.tie(NULL);
33 using namespace std;
34 
35 
36 int d[111],x[111],s[111];
37 char a[111];
38 int main()
39 {
40     int n;
41     cin>>n;
42     for(int i=0;i<n;i++)
43     {
44         memset(a,0);
45         memset(d,0);
46         memset(x,0);
47         memset(s,0);
48         cin>>a;
49         int l=strlen(a);
50         int ansd=0,ansx=0,anss=0;
51         int y=-1,yy=-1,yyy=-1;
52         for(int j=0;j<l;j++)
53         {
54             if(a[j]>='a'&&a[j]<='z')
55             {
56                 y=j;
57                 x[ansx++]=j;
58             }
59             if(a[j]>='A'&&a[j]<='Z')
60             {
61                 yy=j;
62                 d[ansd++]=j;
63             }
64             if(a[j]>='0'&&a[j]<='9')
65             {
66                 yyy=j;
67                 s[anss++]=j;
68             }
69         }
70         if(y==-1)
71         {
72             if(ansd>=2)
73                 a[d[--ansd]]='a';
74             else
75                 a[s[--anss]]='a';
76         }
77         if(yy==-1)
78         {
79             if(ansx>=2)
80                 a[x[--ansx]]='A';
81             else
82                 a[s[--anss]]='A';
83         }
84         if(yyy==-1)
85         {
86             if(ansx>=2)
87                 a[x[--ansx]]='1';
88             else
89                 a[d[--ansd]]='1';
90         }
91         cout<<a<<endl;
92     }
93     return 0;
94 }

View Code