IntelCodeChallengeEliminationRound(Div.1+Div.2,combined)ABCD水模拟并查集优先队列 ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

IntelCodeChallengeEliminationRound(Div.1+Div.2,combined)ABCD水模拟并查集优先队列 ...

原作者: [db:作者] 来自: [db:来源] 收藏邀请

You are given a broken clock. You know, that it is supposed to show time in 12- or 24-hours HH:MM format. In 12-hours format hours change from 1 to 12, while in 24-hours it changes from 0 to 23. In both formats minutes change from 0 to 59.

You are given a time in format HH:MM that is currently displayed on the broken clock. Your goal is to change minimum number of digits in order to make clocks display the correct time in the given format.

For example, if 00:99 is displayed, it is enough to replace the second 9 with 3 in order to get 00:39 that is a correct time in 24-hours format. However, to make 00:99 correct in 12-hours format, one has to change at least two digits. Additionally to the first change one can replace the second 0 with 1 and obtain 01:39.

Input

The first line of the input contains one integer 12 or 24, that denote 12-hours or 24-hours format respectively.

The second line contains the time in format HH:MM, that is currently displayed on the clock. First two characters stand for the hours, while next two show the minutes.

Output

The only line of the output should contain the time in format HH:MM that is a correct time in the given format. It should differ from the original in as few positions as possible. If there are many optimal solutions you can print any of them.

Examples

Input

24
17:30

Output

17:30

Input

12
17:30

Output

07:30

Input

24
99:99

Output

09:09
题意：12/24计时方法下 对于非法的时间 更改最少的位数 使得合法并输出
题解：水
注意数据
12
30:00

 1 /******************************
 2 code by drizzle
 3 blog: www.cnblogs.com/hsd-/
 4 ^ ^    ^ ^
 5  O      O
 6 ******************************/
 7 #include<bits/stdc++.h>
 8 #include<map>
 9 #include<set>
10 #include<cmath>
11 #include<queue>
12 #include<bitset>
13 #include<math.h>
14 #include<vector>
15 #include<string>
16 #include<stdio.h>
17 #include<cstring>
18 #include<iostream>
19 #include<algorithm>
20 #pragma comment(linker, "/STACK:102400000,102400000")
21 using namespace std;
22 #define  A first
23 #define B second
24 const int mod=1000000007;
25 const int MOD1=1000000007;
26 const int MOD2=1000000009;
27 const double EPS=0.00000001;
28 //typedef long long ll;
29 typedef __int64 ll;
30 const ll MOD=1000000007;
31 const int INF=1000000010;
32 const ll MAX=1ll<<55;
33 const double eps=1e-5;
34 const double inf=~0u>>1;
35 const double pi=acos(-1.0);
36 typedef double db;
37 typedef unsigned int uint;
38 typedef unsigned long long ull;
39 int what;
40 char a[10];
41 int main()
42 {
43     scanf("%d",&what);
44     getchar();
45     scanf("%s",a);
46     if(what==24)
47     {
48         int s,t;
49         s=(a[0]-'0')*10+(a[1]-'0');
50         t=(a[3]-'0')*10+(a[4]-'0');
51         //cout<<s<<" "<<t<<endl;
52         if(s>23)
53             a[0]='0';
54         if(t>59)
55             a[3]='0';
56     }
57     else
58     {
59         int s,t;
60         s=(a[0]-'0')*10+a[1]-'0';
61         t=(a[3]-'0')*10+a[4]-'0';
62         if(s==0)
63             a[0]='1';
64         if(s>12)
65           {
66                if(a[1]=='0')
67                 a[0]='1';
68                else
69                 a[0]='0';
70           }
71         if(t>59)
72             a[3]='0';
73     }
74     cout<<a<<endl;
75     return 0;
76 }

You are given a text consisting of n lines. Each line contains some space-separated words, consisting of lowercase English letters.

We define a syllable as a string that contains exactly one vowel and any arbitrary number (possibly none) of consonants. In English alphabet following letters are considered to be vowels: 'a', 'e', 'i', 'o', 'u' and 'y'.

Each word of the text that contains at least one vowel can be divided into syllables. Each character should be a part of exactly one syllable. For example, the word "mamma" can be divided into syllables as "ma" and "mma", "mam" and "ma", and "mamm" and "a". Words that consist of only consonants should be ignored.

The verse patterns for the given text is a sequence of n integers p₁, p₂, ..., p_n. Text matches the given verse pattern if for each i from 1 to n one can divide words of the i-th line in syllables in such a way that the total number of syllables is equal to p_i.

You are given the text and the verse pattern. Check, if the given text matches the given verse pattern.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100) — the number of lines in the text.

The second line contains integers p₁, ..., p_n (0 ≤ p_i ≤ 100) — the verse pattern.

Next n lines contain the text itself. Text consists of lowercase English letters and spaces. It's guaranteed that all lines are non-empty, each line starts and ends with a letter and words are separated by exactly one space. The length of each line doesn't exceed 100 characters.

Output

If the given text matches the given verse pattern, then print "YES" (without quotes) in the only line of the output. Otherwise, print "NO" (without quotes).

Examples

Input

3
2 2 3
intel
code
ch allenge

Output

YES

Input

4
1 2 3 1
a
bcdefghi
jklmnopqrstu
vwxyz

Output

NO

Input

4
13 11 15 15
to be or not to be that is the question
whether tis nobler in the mind to suffer
the slings and arrows of outrageous fortune
or to take arms against a sea of troubles

Output

YES

Note

In the first sample, one can split words into syllables in the following way:

in-tel
co-de
ch al-len-ge

Since the word "ch" in the third line doesn't contain vowels, we can ignore it. As the result we get 2 syllabels in first two lines and 3 syllables in the third one.

题意:统计aeiouy的个数一一对应则输出YES 否则输出NO

题解:模拟

 1 /******************************
 2 code by drizzle
 3 blog: www.cnblogs.com/hsd-/
 4 ^ ^    ^ ^
 5  O      O
 6 ******************************/
 7 #include<bits/stdc++.h>
 8 #include<map>
 9 #include<set>
10 #include<cmath>
11 #include<queue>
12 #include<bitset>
13 #include<math.h>
14 #include<vector>
15 #include<string>
16 #include<stdio.h>
17 #include<cstring>
18 #include<iostream>
19 #include<algorithm>
20 #pragma comment(linker, "/STACK:102400000,102400000")
21 using namespace std;
22 #define  A first
23 #define B second
24 const int mod=1000000007;
25 const int MOD1=1000000007;
26 const int MOD2=1000000009;
27 const double EPS=0.00000001;
28 //typedef long long ll;
29 typedef __int64 ll;
30 const ll MOD=1000000007;
31 const int INF=1000000010;
32 const ll MAX=1ll<<55;
33 const double eps=1e-5;
34 const double inf=~0u>>1;
35 const double pi=acos(-1.0);
36 typedef double db;
37 typedef unsigned int uint;
38 typedef unsigned long long ull;
39 int n;
40 int  a[105];
41 char b[105][105];
42 map<char,int>mp;
43 int main()
44 {
45     mp['a']=1;
46     mp['e']=1;
47     mp['i']=1;
48     mp['o']=1;
49     mp['u']=1;
50     mp['y']=1;
51     scanf("%d",&n);
52     int flag=0;
53     memset(b,0,sizeof(b));
54     for(int i=1;i<=n;i++)
55         scanf("%d",&a[i]);
56     getchar();
57     for(int i=1;i<=n;i++)
58     {
59         gets(b[i]);
60         int ans=0;
61         int len=strlen(b[i]);
62         for(int j=0;j<len;j++)
63         {
64             if(mp[b[i][j]])
65                 ans++;
66         }
67         if(ans!=a[i])
68             flag=1;
69     }
70     if(flag)
71         cout<<"NO"<<endl;
72     else
73         cout<<"YES"<<endl;
74     return 0;
75 }

You are given an array consisting of n non-negative integers a₁, a₂, ..., a_n.

You are going to destroy integers in the array one by one. Thus, you are given the permutation of integers from 1 to n defining the order elements of the array are destroyed.

After each element is destroyed you have to find out the segment of the array, such that it contains no destroyed elements and the sum of its elements is maximum possible. The sum of elements in the empty segment is considered to be 0.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the length of the array.

The second line contains n integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁹).

The third line contains a permutation of integers from 1 to n — the order used to destroy elements.

Output

Print n lines. The i-th line should contain a single integer — the maximum possible sum of elements on the segment containing no destroyed elements, after first i operations are performed.

Examples

Input

4
1 3 2 5
3 4 1 2

Output

Input

5
1 2 3 4 5
4 2 3 5 1

Output

Input

8
5 5 4 4 6 6 5 5
5 2 8 7 1 3 4 6

Output

Note

Consider the first sample:

Third element is destroyed. Array is now 1 3 * 5. Segment with maximum sum 5 consists of one integer 5.
Fourth element is destroyed. Array is now 1 3 * * . Segment with maximum sum 4 consists of two integers 1 3.
First element is destroyed. Array is now * 3 * * . Segment with maximum sum 3 consists of one integer 3.
Last element is destroyed. At this moment there are no valid nonempty segments left in this array, so the answer is equal to 0.

题意：给你n个数并给出删除这n个数的次序对于每次删除输出连续区间(不包括删除的位置的数)的和的最大值

题解：逆向来思考正向的删除当作逆向的增加每增加一个数判断是否与已知的集合相邻或者作为新的集合取max输出并查集处理

 1 /******************************
 2 code by drizzle
 3 blog: www.cnblogs.com/hsd-/
 4 ^ ^    ^ ^
 5  O      O
 6 ******************************/
 7 #include<bits/stdc++.h>
 8 #include<map>
 9 #include<set>
10 #include<cmath>
11 #include<queue>
12 #include<bitset>
13 #include<math.h>
14 #include<vector>
15 #include<string>
16 #include<stdio.h>
17 #include<cstring>
18 #include<iostream>
19 #include<algorithm>
20 #pragma comment(linker, "/STACK:102400000,102400000")
21 using namespace std;
22 #define  A first
23 #define B second
24 const int mod=1000000007;
25 const int MOD1=1000000007;
26 const int MOD2=1000000009;
27 const double EPS=0.00000001;
28 //typedef long long ll;
29 typedef __int64 ll;
30 const ll MOD=1000000007;
31 const int INF=1000000010;
32 const ll MAX=1ll<<55;
33 const double eps=1e-5;
34 const double inf=~0u>>1;
35 const double pi=acos(-1.0);
36 typedef double db;
37 typedef unsigned int uint;
38 typedef unsigned long long ull;
39 int n;
40 ll a[100005];
41 ll s[100005];
42 int used[100005];
43 int pos[100005];
44 int fa[100005];
45 ll re[100005];
46 int find(int root)
47 {
48     if(fa[root]!=root)
49         fa[root]=find(fa[root]);
50     return fa[root];
51 }
52 void uni(int a,int b)
53 {
54     int aa=find(a);
55     int bb=find(b);
56     if(aa!=bb)
57     {
58         fa[aa]=bb;
59         s[bb]+=s[aa];
60     }
61 }
62 int main()
63 {
64     scanf("%d",&n);
65     for(int i=1; i<=n; i++)
66     {
67         scanf("%I64d",&a[i]);
68         fa[i]=i;
69     }
70     for(int i=1; i<=n; i++)
71         scanf("%d",&pos[i]);
72     ll ans=0;
73     for(int i=n; i>=1; i--)
74     {
75         s[pos[i]]=a[pos[i]];
76         used[pos[i]]=1;
77         if(pos[i]<n&&used[pos[i]+1])
78             uni(pos[i],pos[i]+1);
79         if(pos[i]>1&&used[pos[i]-1])
80             uni(pos[i],pos[i]-1);
81         re[i]=ans;
82         ans=max(ans,s[find(pos[i])]);
83     }
84     for(int i=1; i<=n; i++)
85         printf("%I64d\n",re[i]);
86     return 0;
87 }

You are given a set Y of n distinct positive integers y₁, y₂, ..., y_n.

Set X of n distinct positive integers x₁, x₂, ..., x_n is said to generate set Y if one can transform X to Y by applying some number of the following two operation to integers in X:

Take any integer x_i and multiply it by two, i.e. replace x_i with 2·x_i.
Take any integer x_i, multiply it by two and add one, i.e. replace x_i with 2·x_i + 1.

Note that integers in X are not required to be distinct after each operation.

Two sets of distinct integers X and Y are equal if they are equal as sets. In other words, if we write elements of the sets in the array in the increasing order, these arrays would be equal.

Note, that any set of integers (or its permutation) generates itself.

You are given a set Y and have to find a set X that generates Y and the maximum element of X is mininum possible.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 50 000) — the number of elements in Y.

The second line contains n integers y₁, ..., y_n (1 ≤ y_i ≤ 10⁹), that are guaranteed to be distinct.

Output

Print n integers — set of distinct integers that generate Y and the maximum element of which is minimum possible. If there are several such sets, print any of them.

Examples

Input

5
1 2 3 4 5

Output

4 5 2 3 1

Input

6
15 14 3 13 1 12

Output

12 13 14 7 3 1

Input

6
9 7 13 17 5 11

Output

4 5 2 6 3 1 

题意：给你集合y 要求集合x  x,y中的元素的都是不同的  集合x可以通过集合内的元素xi不断更新为2*xi或2*xi+1 同一个x只能变为y中的一个数 从而获得集合y
输出满足条件的集合x 要求x的最大值尽量小
题解：优先队列处理

 1 /******************************
 2 code by drizzle
 3 blog: www.cnblogs.com/hsd-/
 4 ^ ^    ^ ^
 5  O      O
 6 ******************************/
 7 #include<bits/stdc++.h>
 8 #include<map>
 9 #include<set>
10 #include<cmath>
11 #include<queue>
12 #include<bitset>
13 #include<math.h>
14 #include<vector>
15 #include<string>
16 #include<stdio.h>
17 #include<cstring>
18 #include<iostream>
19 #include<algorithm>
20 #pragma comment(linker, "/STACK:102400000,102400000")
21 using namespace std;
22 #define  A first
23 #define B second
24 const int mod=1000000007;
25 const int MOD1=1000000007;
26 const int MOD2=1000000009;
27 const double EPS= 
                       
                    
                     
                      



鲜花




握手




雷人




路过




鸡蛋

该文章已有0人参与评论

请发表评论

全部评论

专题导读

More+

10-27 六六分期app的软件客服如何联系？(六六分期

11-06 可心卡盟:win10系统火狐flash插件崩溃怎么

11-06 亲亲特价:怎么删除回收站图标

11-06 济南大学虚拟社区:鲁大师节能降温的具体办

11-06 xlueops.exe:无线网络安装向导

11-06 女斗合众国:win7系统cf与主机连接不稳定怎

11-06 0xc000022-[cf烟雾头]cf怎么调烟雾头

11-06 qizideyouhuo:应用程序无法正常启动0xc0000

11-06 ipz-185:win7系统vcf文件怎么打开

11-06 傻哥蹦迪:win10系统s4怎么打开usb调试

11-06 八神浩树gtaste:回收站清空了怎么恢复

11-06 妖尾之黑色守护:win10系统电脑没有1440x900

11-06 校园至尊魔王小说:win7系统浏览网页时字体

11-06 女斗合众国:win10系统访问共享文件夹提示请

11-06 tokyo hot n0654:恢复win7系统默认字体一招

11-06 雨酷仙境:设置win7系统转移临时文件夹腾出

11-06 阿穆纳伊之杖:win7系统开始菜单在右边还原

11-06 tunespotting:win10系统火狐flash插件总是

11-06 甘尔葛分析师：计谋网站seo关键词暴涨有什

11-06 蔡贵霖: 计谋网站seo关键词暴涨有什么秘密

11-06 博益网首页:ao3网页版进入不了解决方法

11-06 漏斗子专栏: 网站数据分析小白易懂精华篇

11-06 见证双虹怎么做:win7系统开启telnet命令的

11-06 颾狐蝶蜋:系统资源不足无法完成请求的服务

11-06 国光中学校歌:提交网站到alexa查询详细步骤

11-06 西安有情天:静态网页和动态网页的区别

11-06 红木雅尚斋:外部链接构造对网站的好处

11-06 前官礼遇：防止域名劫持–增强域安全性的10

11-06 密传二转答案: 中文分词算法有哪些

11-06 金泉家园邮编:百度快照劫持的表现及应对方

加载rocksdb实例报错：java.lang.UnsatisfiedLinkError:C:\Users\Administrator\AppDa ...发布时间：2022-07-14

.NETC#基础（5）：结构体-高性能代码的基石发布时间：2022-07-14

剪的笔顺,诠释剪的笔画,认识剪的部首

1 六六分期app的软件客服如何联系？(六六分期

六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期

阅读：19170|2023-10-27

2 可心卡盟:win10系统火狐flash插件崩溃怎么

今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知

阅读：9982|2022-11-06

3 亲亲特价:怎么删除回收站图标

今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道

阅读：8322|2022-11-06

4 济南大学虚拟社区:鲁大师节能降温的具体办

今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要

阅读：8691|2022-11-06

5 xlueops.exe:无线网络安装向导

我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多

阅读：8635|2022-11-06

6 女斗合众国:win7系统cf与主机连接不稳定怎

今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不

阅读：9651|2022-11-06

7 0xc000022-[cf烟雾头]cf怎么调烟雾头

电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很

阅读：8618|2022-11-06

8 qizideyouhuo:应用程序无法正常启动0xc0000

我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法

阅读：7995|2022-11-06

9 ipz-185:win7系统vcf文件怎么打开

今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win

阅读：8649|2022-11-06

10 傻哥蹦迪:win10系统s4怎么打开usb调试

今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎

阅读：7532|2022-11-06

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服（服务时间 9:00～18:00）

在线QQ客服

地址：深圳市南山区西丽大学城创智工业园

电邮：jeky_zhao#qq.com

移动电话：139-2527-9053

客服电话

电子邮件

IntelCodeChallengeEliminationRound(Div.1+Div.2,combined)ABCD水模拟并查集优先队列 ...

请发表评论

全部评论

上一篇：

下一篇：

CVE-2022-32051

xorrior/macOSTools: macOS Offensive Tool

caseypugh/minecraft: Some scripts to mak

Testinium/MobileDeviceInfo

xsfelvis/MaterialDesignStudy: A practic

剪的笔顺,诠释剪的笔画,认识剪的部首

六六分期app的软件客服如何联系？(六六分期

florent37/ViewAnimator: A fluent Android

florent37/Shrine-MaterialDesign2: implem

CVE-2020-36276

SimpleSoftwareIO/simple-sms: Send and re

关于我们

产品与服务

解决方案

139-2527-9053