; LLVM IR from tangjz/acm-icpc :: hdu (5340)

; Unoptimized IR (clang -disable-llvm-passes):
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

%struct.Bitset = type { i32, i64, [313 x i64] }

@t = external dso_local global i32, align 4
@n = external dso_local global i32, align 4
@h = external dso_local global [40020 x i32], align 16
@lbt = external dso_local global [65536 x i32], align 16
@str = external dso_local global [20010 x i8], align 16
@buf = external dso_local global [40021 x i8], align 16
@f = external dso_local global %struct.Bitset, align 8
@g = external dso_local global %struct.Bitset, align 8
@w = external dso_local global %struct.Bitset, align 8
@.str = external hidden unnamed_addr constant [3 x i8], align 1
@.str.1 = external hidden unnamed_addr constant [3 x i8], align 1
@.str.2 = external hidden unnamed_addr constant [4 x i8], align 1
@.str.3 = external hidden unnamed_addr constant [3 x i8], align 1

; Function Attrs: mustprogress norecurse uwtable
define dso_local noundef i32 @main() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  %5 = alloca i32, align 4
  %6 = alloca i32, align 4
  %7 = alloca i32, align 4
  %8 = alloca i32, align 4
  %9 = alloca i8, align 1
  %10 = alloca i32, align 4
  %11 = alloca i32, align 4
  %12 = alloca %struct.Bitset, align 8
  store i32 0, ptr %1, align 4
  call void @llvm.lifetime.start.p0(i64 4, ptr %2) #8
  store i32 1, ptr %2, align 4, !tbaa !5
  br label %13

13:                                               ; preds = %34, %0
  %14 = load i32, ptr %2, align 4, !tbaa !5
  %15 = icmp slt i32 %14, 65536
  br i1 %15, label %17, label %16

16:                                               ; preds = %13
  call void @llvm.lifetime.end.p0(i64 4, ptr %2) #8
  br label %37

17:                                               ; preds = %13
  %18 = load i32, ptr %2, align 4, !tbaa !5
  %19 = and i32 %18, 1
  %20 = icmp ne i32 %19, 0
  br i1 %20, label %21, label %22

21:                                               ; preds = %17
  br label %29

22:                                               ; preds = %17
  %23 = load i32, ptr %2, align 4, !tbaa !5
  %24 = ashr i32 %23, 1
  %25 = sext i32 %24 to i64
  %26 = getelementptr inbounds [65536 x i32], ptr @lbt, i64 0, i64 %25
  %27 = load i32, ptr %26, align 4, !tbaa !5
  %28 = add nsw i32 %27, 1
  br label %29

29:                                               ; preds = %22, %21
  %30 = phi i32 [ 0, %21 ], [ %28, %22 ]
  %31 = load i32, ptr %2, align 4, !tbaa !5
  %32 = sext i32 %31 to i64
  %33 = getelementptr inbounds [65536 x i32], ptr @lbt, i64 0, i64 %32
  store i32 %30, ptr %33, align 4, !tbaa !5
  br label %34

34:                                               ; preds = %29
  %35 = load i32, ptr %2, align 4, !tbaa !5
  %36 = add nsw i32 %35, 1
  store i32 %36, ptr %2, align 4, !tbaa !5
  br label %13, !llvm.loop !9

37:                                               ; preds = %16
  %38 = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef @.str, ptr noundef @t)
  br label %39

39:                                               ; preds = %252, %37
  %40 = load i32, ptr @t, align 4, !tbaa !5
  %41 = add nsw i32 %40, -1
  store i32 %41, ptr @t, align 4, !tbaa !5
  %42 = icmp ne i32 %40, 0
  br i1 %42, label %43, label %258

43:                                               ; preds = %39
  %44 = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef @.str.1, ptr noundef @str)
  %45 = call i64 @strlen(ptr noundef @str) #9
  %46 = trunc i64 %45 to i32
  store i32 %46, ptr @n, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %3) #8
  store i32 0, ptr %3, align 4, !tbaa !5
  br label %47

47:                                               ; preds = %66, %43
  %48 = load i32, ptr %3, align 4, !tbaa !5
  %49 = load i32, ptr @n, align 4, !tbaa !5
  %50 = icmp slt i32 %48, %49
  br i1 %50, label %52, label %51

51:                                               ; preds = %47
  call void @llvm.lifetime.end.p0(i64 4, ptr %3) #8
  br label %69

52:                                               ; preds = %47
  %53 = load i32, ptr %3, align 4, !tbaa !5
  %54 = sext i32 %53 to i64
  %55 = getelementptr inbounds [20010 x i8], ptr @str, i64 0, i64 %54
  %56 = load i8, ptr %55, align 1, !tbaa !11
  %57 = load i32, ptr %3, align 4, !tbaa !5
  %58 = shl i32 %57, 1
  %59 = sext i32 %58 to i64
  %60 = getelementptr inbounds [40021 x i8], ptr @buf, i64 0, i64 %59
  store i8 %56, ptr %60, align 1, !tbaa !11
  %61 = load i32, ptr %3, align 4, !tbaa !5
  %62 = shl i32 %61, 1
  %63 = or i32 %62, 1
  %64 = sext i32 %63 to i64
  %65 = getelementptr inbounds [40021 x i8], ptr @buf, i64 0, i64 %64
  store i8 35, ptr %65, align 1, !tbaa !11
  br label %66

66:                                               ; preds = %52
  %67 = load i32, ptr %3, align 4, !tbaa !5
  %68 = add nsw i32 %67, 1
  store i32 %68, ptr %3, align 4, !tbaa !5
  br label %47, !llvm.loop !12

69:                                               ; preds = %51
  %70 = load i32, ptr @n, align 4, !tbaa !5
  %71 = shl i32 %70, 1
  %72 = sext i32 %71 to i64
  %73 = getelementptr inbounds [40021 x i8], ptr @buf, i64 0, i64 %72
  store i8 0, ptr %73, align 1, !tbaa !11
  call void @llvm.lifetime.start.p0(i64 4, ptr %4) #8
  store i32 0, ptr %4, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %5) #8
  store i32 0, ptr %5, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 4, ptr %6) #8
  store i32 0, ptr %6, align 4, !tbaa !5
  br label %74

74:                                               ; preds = %159, %69
  %75 = load i32, ptr %4, align 4, !tbaa !5
  %76 = load i32, ptr @n, align 4, !tbaa !5
  %77 = sub nsw i32 %76, 1
  %78 = shl i32 %77, 1
  %79 = icmp sle i32 %75, %78
  br i1 %79, label %81, label %80

80:                                               ; preds = %74
  call void @llvm.lifetime.end.p0(i64 4, ptr %6) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %5) #8
  call void @llvm.lifetime.end.p0(i64 4, ptr %4) #8
  br label %162

81:                                               ; preds = %74
  %82 = load i32, ptr %4, align 4, !tbaa !5
  %83 = load i32, ptr %5, align 4, !tbaa !5
  %84 = icmp slt i32 %82, %83
  call void @llvm.lifetime.start.p0(i64 4, ptr %7) #8
  br i1 %84, label %85, label %97

85:                                               ; preds = %81
  %86 = load i32, ptr %5, align 4, !tbaa !5
  %87 = load i32, ptr %4, align 4, !tbaa !5
  %88 = sub nsw i32 %86, %87
  store i32 %88, ptr %7, align 4, !tbaa !5
  %89 = load i32, ptr %6, align 4, !tbaa !5
  %90 = shl i32 %89, 1
  %91 = load i32, ptr %4, align 4, !tbaa !5
  %92 = sub nsw i32 %90, %91
  %93 = sext i32 %92 to i64
  %94 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %93
  %95 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZSt3minIiERKT_S2_S2_(ptr noundef nonnull align 4 dereferenceable(4) %7, ptr noundef nonnull align 4 dereferenceable(4) %94)
  %96 = load i32, ptr %95, align 4, !tbaa !5
  br label %98

97:                                               ; preds = %81
  br label %98

98:                                               ; preds = %97, %85
  %99 = phi i32 [ %96, %85 ], [ 0, %97 ]
  %100 = load i32, ptr %4, align 4, !tbaa !5
  %101 = sext i32 %100 to i64
  %102 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %101
  store i32 %99, ptr %102, align 4, !tbaa !5
  call void @llvm.lifetime.end.p0(i64 4, ptr %7) #8
  br label %103

103:                                              ; preds = %135, %98
  %104 = load i32, ptr %4, align 4, !tbaa !5
  %105 = sext i32 %104 to i64
  %106 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %105
  %107 = load i32, ptr %106, align 4, !tbaa !5
  %108 = load i32, ptr %4, align 4, !tbaa !5
  %109 = icmp sle i32 %107, %108
  br i1 %109, label %110, label %132

110:                                              ; preds = %103
  %111 = load i32, ptr %4, align 4, !tbaa !5
  %112 = load i32, ptr %4, align 4, !tbaa !5
  %113 = sext i32 %112 to i64
  %114 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %113
  %115 = load i32, ptr %114, align 4, !tbaa !5
  %116 = sub nsw i32 %111, %115
  %117 = sext i32 %116 to i64
  %118 = getelementptr inbounds [40021 x i8], ptr @buf, i64 0, i64 %117
  %119 = load i8, ptr %118, align 1, !tbaa !11
  %120 = sext i8 %119 to i32
  %121 = load i32, ptr %4, align 4, !tbaa !5
  %122 = load i32, ptr %4, align 4, !tbaa !5
  %123 = sext i32 %122 to i64
  %124 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %123
  %125 = load i32, ptr %124, align 4, !tbaa !5
  %126 = add nsw i32 %121, %125
  %127 = sext i32 %126 to i64
  %128 = getelementptr inbounds [40021 x i8], ptr @buf, i64 0, i64 %127
  %129 = load i8, ptr %128, align 1, !tbaa !11
  %130 = sext i8 %129 to i32
  %131 = icmp eq i32 %120, %130
  br label %132

132:                                              ; preds = %110, %103
  %133 = phi i1 [ false, %103 ], [ %131, %110 ]
  br i1 %133, label %134, label %141

134:                                              ; preds = %132
  br label %135

135:                                              ; preds = %134
  %136 = load i32, ptr %4, align 4, !tbaa !5
  %137 = sext i32 %136 to i64
  %138 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %137
  %139 = load i32, ptr %138, align 4, !tbaa !5
  %140 = add nsw i32 %139, 1
  store i32 %140, ptr %138, align 4, !tbaa !5
  br label %103, !llvm.loop !13

141:                                              ; preds = %132
  %142 = load i32, ptr %5, align 4, !tbaa !5
  %143 = load i32, ptr %4, align 4, !tbaa !5
  %144 = load i32, ptr %4, align 4, !tbaa !5
  %145 = sext i32 %144 to i64
  %146 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %145
  %147 = load i32, ptr %146, align 4, !tbaa !5
  %148 = add nsw i32 %143, %147
  %149 = icmp slt i32 %142, %148
  br i1 %149, label %150, label %158

150:                                              ; preds = %141
  %151 = load i32, ptr %4, align 4, !tbaa !5
  %152 = load i32, ptr %4, align 4, !tbaa !5
  %153 = sext i32 %152 to i64
  %154 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %153
  %155 = load i32, ptr %154, align 4, !tbaa !5
  %156 = add nsw i32 %151, %155
  store i32 %156, ptr %5, align 4, !tbaa !5
  %157 = load i32, ptr %4, align 4, !tbaa !5
  store i32 %157, ptr %6, align 4, !tbaa !5
  br label %158

158:                                              ; preds = %150, %141
  br label %159

159:                                              ; preds = %158
  %160 = load i32, ptr %4, align 4, !tbaa !5
  %161 = add nsw i32 %160, 1
  store i32 %161, ptr %4, align 4, !tbaa !5
  br label %74, !llvm.loop !14

162:                                              ; preds = %80
  call void @_ZN6Bitset4initEi(ptr noundef nonnull align 8 dereferenceable(2520) @f, i32 noundef 1)
  call void @_ZN6Bitset3setEm(ptr noundef nonnull align 8 dereferenceable(2520) @f, i64 noundef 0)
  %163 = load i32, ptr @n, align 4, !tbaa !5
  call void @_ZN6Bitset4initEi(ptr noundef nonnull align 8 dereferenceable(2520) @g, i32 noundef %163)
  call void @llvm.lifetime.start.p0(i64 4, ptr %8) #8
  store i32 0, ptr %8, align 4, !tbaa !5
  br label %164

164:                                              ; preds = %186, %162
  %165 = load i32, ptr %8, align 4, !tbaa !5
  %166 = load i32, ptr @n, align 4, !tbaa !5
  %167 = icmp slt i32 %165, %166
  br i1 %167, label %169, label %168

168:                                              ; preds = %164
  call void @llvm.lifetime.end.p0(i64 4, ptr %8) #8
  br label %189

169:                                              ; preds = %164
  %170 = load i32, ptr %8, align 4, !tbaa !5
  %171 = load i32, ptr @n, align 4, !tbaa !5
  %172 = add nsw i32 %170, %171
  %173 = sub nsw i32 %172, 1
  %174 = sext i32 %173 to i64
  %175 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %174
  %176 = load i32, ptr %175, align 4, !tbaa !5
  %177 = load i32, ptr @n, align 4, !tbaa !5
  %178 = load i32, ptr %8, align 4, !tbaa !5
  %179 = sub nsw i32 %177, %178
  %180 = sub nsw i32 %179, 1
  %181 = icmp sgt i32 %176, %180
  br i1 %181, label %182, label %185

182:                                              ; preds = %169
  %183 = load i32, ptr %8, align 4, !tbaa !5
  %184 = sext i32 %183 to i64
  call void @_ZN6Bitset3setEm(ptr noundef nonnull align 8 dereferenceable(2520) @g, i64 noundef %184)
  br label %185

185:                                              ; preds = %182, %169
  br label %186

186:                                              ; preds = %185
  %187 = load i32, ptr %8, align 4, !tbaa !5
  %188 = add nsw i32 %187, 1
  store i32 %188, ptr %8, align 4, !tbaa !5
  br label %164, !llvm.loop !15

189:                                              ; preds = %168
  call void @llvm.lifetime.start.p0(i64 1, ptr %9) #8
  store i8 0, ptr %9, align 1, !tbaa !16
  call void @llvm.lifetime.start.p0(i64 4, ptr %10) #8
  store i32 0, ptr %10, align 4, !tbaa !5
  br label %190

190:                                              ; preds = %249, %189
  %191 = load i32, ptr %10, align 4, !tbaa !5
  %192 = load i32, ptr @n, align 4, !tbaa !5
  %193 = sub nsw i32 %192, 1
  %194 = shl i32 %193, 1
  %195 = icmp sle i32 %191, %194
  br i1 %195, label %196, label %200

196:                                              ; preds = %190
  %197 = load i8, ptr %9, align 1, !tbaa !16, !range !18, !noundef !19
  %198 = trunc i8 %197 to i1
  %199 = xor i1 %198, true
  br label %200

200:                                              ; preds = %196, %190
  %201 = phi i1 [ false, %190 ], [ %199, %196 ]
  br i1 %201, label %203, label %202

202:                                              ; preds = %200
  call void @llvm.lifetime.end.p0(i64 4, ptr %10) #8
  br label %252

203:                                              ; preds = %200
  call void @llvm.lifetime.start.p0(i64 4, ptr %11) #8
  %204 = load i32, ptr %10, align 4, !tbaa !5
  %205 = sext i32 %204 to i64
  %206 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %205
  %207 = load i32, ptr %206, align 4, !tbaa !5
  %208 = load i32, ptr %10, align 4, !tbaa !5
  %209 = and i32 %208, 1
  %210 = sub nsw i32 %207, %209
  %211 = load i32, ptr %10, align 4, !tbaa !5
  %212 = load i32, ptr %10, align 4, !tbaa !5
  %213 = sext i32 %212 to i64
  %214 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %213
  %215 = load i32, ptr %214, align 4, !tbaa !5
  %216 = sub nsw i32 %211, %215
  %217 = xor i32 %216, -1
  %218 = and i32 %217, 1
  %219 = sub nsw i32 %210, %218
  %220 = ashr i32 %219, 1
  store i32 %220, ptr %11, align 4, !tbaa !5
  call void @llvm.lifetime.start.p0(i64 2520, ptr %12) #8
  call void @_ZNK6BitsetanERKS_(ptr dead_on_unwind writable sret(%struct.Bitset) align 8 %12, ptr noundef nonnull align 8 dereferenceable(2520) @f, ptr noundef nonnull align 8 dereferenceable(2520) @g)
  call void @llvm.memcpy.p0.p0.i64(ptr align 8 @w, ptr align 8 %12, i64 2520, i1 false), !tbaa.struct !20
  call void @llvm.lifetime.end.p0(i64 2520, ptr %12) #8
  call void @_ZN6Bitset15shift_right_oneEv(ptr noundef nonnull align 8 dereferenceable(2520) @w)
  %221 = call noundef i32 @_ZNK6Bitset6lowbitEv(ptr noundef nonnull align 8 dereferenceable(2520) @w)
  %222 = load i32, ptr %11, align 4, !tbaa !5
  %223 = icmp sle i32 %221, %222
  %224 = zext i1 %223 to i32
  %225 = load i8, ptr %9, align 1, !tbaa !16, !range !18, !noundef !19
  %226 = trunc i8 %225 to i1
  %227 = zext i1 %226 to i32
  %228 = or i32 %227, %224
  %229 = icmp ne i32 %228, 0
  %230 = zext i1 %229 to i8
  store i8 %230, ptr %9, align 1, !tbaa !16
  %231 = load i32, ptr %10, align 4, !tbaa !5
  %232 = and i32 %231, 1
  %233 = icmp ne i32 %232, 0
  br i1 %233, label %234, label %247

234:                                              ; preds = %203
  call void @_ZN6Bitset14shift_left_oneEv(ptr noundef nonnull align 8 dereferenceable(2520) @f)
  %235 = load i32, ptr %10, align 4, !tbaa !5
  %236 = add nsw i32 %235, 1
  %237 = ashr i32 %236, 1
  %238 = sext i32 %237 to i64
  %239 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %238
  %240 = load i32, ptr %239, align 4, !tbaa !5
  %241 = load i32, ptr %10, align 4, !tbaa !5
  %242 = add nsw i32 %241, 1
  %243 = ashr i32 %242, 1
  %244 = icmp sgt i32 %240, %243
  br i1 %244, label %245, label %246

245:                                              ; preds = %234
  call void @_ZN6Bitset3setEm(ptr noundef nonnull align 8 dereferenceable(2520) @f, i64 noundef 0)
  br label %246

246:                                              ; preds = %245, %234
  br label %248

247:                                              ; preds = %203
  call void @_ZN6Bitset15shift_right_oneEv(ptr noundef nonnull align 8 dereferenceable(2520) @g)
  br label %248

248:                                              ; preds = %247, %246
  call void @llvm.lifetime.end.p0(i64 4, ptr %11) #8
  br label %249

249:                                              ; preds = %248
  %250 = load i32, ptr %10, align 4, !tbaa !5
  %251 = add nsw i32 %250, 1
  store i32 %251, ptr %10, align 4, !tbaa !5
  br label %190, !llvm.loop !23

252:                                              ; preds = %202
  %253 = load i8, ptr %9, align 1, !tbaa !16, !range !18, !noundef !19
  %254 = trunc i8 %253 to i1
  %255 = zext i1 %254 to i64
  %256 = select i1 %254, ptr @.str.2, ptr @.str.3
  %257 = call i32 @puts(ptr noundef %256)
  call void @llvm.lifetime.end.p0(i64 1, ptr %9) #8
  br label %39, !llvm.loop !24

258:                                              ; preds = %39
  ret i32 0
}

; Function Attrs: nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.start.p0(i64 immarg, ptr nocapture) #1

; Function Attrs: nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture) #1

declare i32 @__isoc99_scanf(ptr noundef, ...) #2

; Function Attrs: nounwind willreturn memory(read)
declare i64 @strlen(ptr noundef) #3

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(4) ptr @_ZSt3minIiERKT_S2_S2_(ptr noundef nonnull align 4 dereferenceable(4), ptr noundef nonnull align 4 dereferenceable(4)) #4

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZN6Bitset4initEi(ptr noundef nonnull align 8 dereferenceable(2520), i32 noundef) #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZN6Bitset3setEm(ptr noundef nonnull align 8 dereferenceable(2520), i64 noundef) #5 align 2

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZNK6BitsetanERKS_(ptr dead_on_unwind noalias writable sret(%struct.Bitset) align 8, ptr noundef nonnull align 8 dereferenceable(2520), ptr noundef nonnull align 8 dereferenceable(2520)) #6 align 2

; Function Attrs: nocallback nofree nounwind willreturn memory(argmem: readwrite)
declare void @llvm.memcpy.p0.p0.i64(ptr noalias nocapture writeonly, ptr noalias nocapture readonly, i64, i1 immarg) #7

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZN6Bitset15shift_right_oneEv(ptr noundef nonnull align 8 dereferenceable(2520)) #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef i32 @_ZNK6Bitset6lowbitEv(ptr noundef nonnull align 8 dereferenceable(2520)) #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZN6Bitset14shift_left_oneEv(ptr noundef nonnull align 8 dereferenceable(2520)) #5 align 2

declare i32 @puts(ptr noundef) #2

attributes #0 = { mustprogress norecurse uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }
attributes #2 = { "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #3 = { nounwind willreturn memory(read) "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #4 = { inlinehint mustprogress nounwind uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #5 = { mustprogress nounwind uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #6 = { mustprogress uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #7 = { nocallback nofree nounwind willreturn memory(argmem: readwrite) }
attributes #8 = { nounwind }
attributes #9 = { nounwind willreturn memory(read) }

!llvm.module.flags = !{!0, !1, !2, !3}
!llvm.ident = !{!4}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{!"clang version 19.1.0 (git@github.com:llvm/llvm-project.git a4bf6cd7cfb1a1421ba92bca9d017b49936c55e4)"}
!5 = !{!6, !6, i64 0}
!6 = !{!"int", !7, i64 0}
!7 = !{!"omnipotent char", !8, i64 0}
!8 = !{!"Simple C++ TBAA"}
!9 = distinct !{!9, !10}
!10 = !{!"llvm.loop.mustprogress"}
!11 = !{!7, !7, i64 0}
!12 = distinct !{!12, !10}
!13 = distinct !{!13, !10}
!14 = distinct !{!14, !10}
!15 = distinct !{!15, !10}
!16 = !{!17, !17, i64 0}
!17 = !{!"bool", !7, i64 0}
!18 = !{i8 0, i8 2}
!19 = !{}
!20 = !{i64 0, i64 4, !5, i64 8, i64 8, !21, i64 16, i64 2504, !11}
!21 = !{!22, !22, i64 0}
!22 = !{!"long", !7, i64 0}
!23 = distinct !{!23, !10}
!24 = distinct !{!24, !10}


; Optimized IR (opt -passes='default<O3>'):
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

%struct.Bitset = type { i32, i64, [313 x i64] }

@t = external dso_local global i32, align 4
@n = external dso_local local_unnamed_addr global i32, align 4
@h = external dso_local global [40020 x i32], align 16
@lbt = external dso_local local_unnamed_addr global [65536 x i32], align 16
@str = external dso_local global [20010 x i8], align 16
@buf = external dso_local local_unnamed_addr global [40021 x i8], align 16
@f = external dso_local global %struct.Bitset, align 8
@g = external dso_local global %struct.Bitset, align 8
@w = external dso_local global %struct.Bitset, align 8
@.str = external hidden unnamed_addr constant [3 x i8], align 1
@.str.1 = external hidden unnamed_addr constant [3 x i8], align 1
@.str.2 = external hidden unnamed_addr constant [4 x i8], align 1
@.str.3 = external hidden unnamed_addr constant [3 x i8], align 1

; Function Attrs: mustprogress norecurse uwtable
define dso_local noundef i32 @main() local_unnamed_addr #0 {
  %1 = alloca i32, align 4
  %2 = alloca %struct.Bitset, align 8
  br label %7

3:                                                ; preds = %7
  %4 = tail call i32 (ptr, ...) @__isoc99_scanf(ptr noundef nonnull @.str, ptr noundef nonnull @t)
  %5 = load i32, ptr @t, align 4, !tbaa !5
  %6 = add nsw i32 %5, -1
  store i32 %6, ptr @t, align 4, !tbaa !5
  %.not93 = icmp eq i32 %5, 0
  br i1 %.not93, label %._crit_edge96, label %.lr.ph95

7:                                                ; preds = %9, %0
  %indvars.iv = phi i64 [ 1, %0 ], [ %indvars.iv.next.1, %9 ]
  %8 = getelementptr inbounds [65536 x i32], ptr @lbt, i64 0, i64 %indvars.iv
  store i32 0, ptr %8, align 4, !tbaa !5
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond.not = icmp eq i64 %indvars.iv.next, 65536
  br i1 %exitcond.not, label %3, label %9, !llvm.loop !9

9:                                                ; preds = %7
  %10 = lshr exact i64 %indvars.iv.next, 1
  %11 = getelementptr inbounds [65536 x i32], ptr @lbt, i64 0, i64 %10
  %12 = load i32, ptr %11, align 4, !tbaa !5
  %13 = add nsw i32 %12, 1
  %14 = getelementptr inbounds [65536 x i32], ptr @lbt, i64 0, i64 %indvars.iv.next
  store i32 %13, ptr %14, align 4, !tbaa !5
  %indvars.iv.next.1 = add nuw nsw i64 %indvars.iv, 2
  br label %7

.lr.ph95:                                         ; preds = %3, %._crit_edge91.thread
  %15 = call i32 (ptr, ...) @__isoc99_scanf(ptr noundef nonnull @.str.1, ptr noundef nonnull @str)
  %16 = call i64 @strlen(ptr noundef nonnull dereferenceable(1) @str) #9
  %17 = trunc i64 %16 to i32
  store i32 %17, ptr @n, align 4, !tbaa !5
  %18 = icmp sgt i32 %17, 0
  br i1 %18, label %.lr.ph.preheader, label %._crit_edge

.lr.ph.preheader:                                 ; preds = %.lr.ph95
  %wide.trip.count = and i64 %16, 2147483647
  %min.iters.check = icmp ult i64 %wide.trip.count, 24
  br i1 %min.iters.check, label %.lr.ph.preheader137, label %vector.scevcheck

.lr.ph.preheader137:                              ; preds = %middle.block, %vector.scevcheck, %.lr.ph.preheader
  %indvars.iv99.ph = phi i64 [ 0, %vector.scevcheck ], [ 0, %.lr.ph.preheader ], [ %n.vec, %middle.block ]
  %19 = sub i64 %16, %indvars.iv99.ph
  %.neg = add nsw i64 %indvars.iv99.ph, 1
  %xtraiter = and i64 %19, 1
  %lcmp.mod.not = icmp eq i64 %xtraiter, 0
  br i1 %lcmp.mod.not, label %.lr.ph.prol.loopexit, label %.lr.ph.prol

.lr.ph.prol:                                      ; preds = %.lr.ph.preheader137
  %20 = getelementptr inbounds [20010 x i8], ptr @str, i64 0, i64 %indvars.iv99.ph
  %21 = load i8, ptr %20, align 1, !tbaa !11
  %sext.prol = shl i64 %indvars.iv99.ph, 33
  %22 = ashr exact i64 %sext.prol, 32
  %23 = getelementptr inbounds [40021 x i8], ptr @buf, i64 0, i64 %22
  store i8 %21, ptr %23, align 2, !tbaa !11
  %indvars.iv99.tr.prol = trunc i64 %indvars.iv99.ph to i32
  %24 = shl i32 %indvars.iv99.tr.prol, 1
  %25 = or disjoint i32 %24, 1
  %26 = sext i32 %25 to i64
  %27 = getelementptr inbounds [40021 x i8], ptr @buf, i64 0, i64 %26
  store i8 35, ptr %27, align 1, !tbaa !11
  %indvars.iv.next100.prol = add nuw nsw i64 %indvars.iv99.ph, 1
  br label %.lr.ph.prol.loopexit

.lr.ph.prol.loopexit:                             ; preds = %.lr.ph.prol, %.lr.ph.preheader137
  %indvars.iv99.unr = phi i64 [ %indvars.iv99.ph, %.lr.ph.preheader137 ], [ %indvars.iv.next100.prol, %.lr.ph.prol ]
  %28 = icmp eq i64 %wide.trip.count, %.neg
  br i1 %28, label %._crit_edge, label %.lr.ph

vector.scevcheck:                                 ; preds = %.lr.ph.preheader
  %29 = add nsw i64 %wide.trip.count, -1
  %30 = and i64 %29, -3221225472
  %31 = icmp ne i64 %30, 0
  %mul.result129 = shl nsw i64 %29, 1
  %32 = getelementptr i8, ptr @buf, i64 %mul.result129
  %33 = icmp ult ptr %32, @buf
  %mul.result132 = shl nsw i64 %29, 1
  %34 = getelementptr i8, ptr getelementptr inbounds (i8, ptr @buf, i64 1), i64 %mul.result132
  %35 = icmp ult ptr %34, getelementptr inbounds (i8, ptr @buf, i64 1)
  %36 = or i1 %31, %33
  %37 = or i1 %36, %35
  br i1 %37, label %.lr.ph.preheader137, label %vector.ph

vector.ph:                                        ; preds = %vector.scevcheck
  %n.mod.vf = and i64 %16, 15
  %n.vec = sub nsw i64 %wide.trip.count, %n.mod.vf
  br label %vector.body

vector.body:                                      ; preds = %vector.body, %vector.ph
  %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
  %38 = trunc i64 %index to i32
  %39 = getelementptr inbounds [20010 x i8], ptr @str, i64 0, i64 %index
  %40 = getelementptr inbounds i8, ptr %39, i64 8
  %wide.load = load <8 x i8>, ptr %39, align 16, !tbaa !11
  %wide.load134 = load <8 x i8>, ptr %40, align 8, !tbaa !11
  %41 = shl i32 %38, 1
  %42 = shl i32 %38, 1
  %43 = or disjoint i32 %41, 1
  %44 = or disjoint i32 %42, 17
  %45 = sext i32 %43 to i64
  %46 = sext i32 %44 to i64
  %gep = getelementptr [40021 x i8], ptr getelementptr (i8, ptr @buf, i64 -1), i64 0, i64 %45
  %gep144 = getelementptr [40021 x i8], ptr getelementptr (i8, ptr @buf, i64 -1), i64 0, i64 %46
  %interleaved.vec = shufflevector <8 x i8> %wide.load, <8 x i8> <i8 35, i8 35, i8 35, i8 35, i8 35, i8 35, i8 35, i8 35>, <16 x i32> <i32 0, i32 8, i32 1, i32 9, i32 2, i32 10, i32 3, i32 11, i32 4, i32 12, i32 5, i32 13, i32 6, i32 14, i32 7, i32 15>
  store <16 x i8> %interleaved.vec, ptr %gep, align 2, !tbaa !11
  %interleaved.vec135 = shufflevector <8 x i8> %wide.load134, <8 x i8> <i8 35, i8 35, i8 35, i8 35, i8 35, i8 35, i8 35, i8 35>, <16 x i32> <i32 0, i32 8, i32 1, i32 9, i32 2, i32 10, i32 3, i32 11, i32 4, i32 12, i32 5, i32 13, i32 6, i32 14, i32 7, i32 15>
  store <16 x i8> %interleaved.vec135, ptr %gep144, align 2, !tbaa !11
  %index.next = add nuw i64 %index, 16
  %47 = icmp eq i64 %index.next, %n.vec
  br i1 %47, label %middle.block, label %vector.body, !llvm.loop !12

middle.block:                                     ; preds = %vector.body
  %cmp.n = icmp eq i64 %n.mod.vf, 0
  br i1 %cmp.n, label %._crit_edge, label %.lr.ph.preheader137

._crit_edge:                                      ; preds = %.lr.ph.prol.loopexit, %.lr.ph, %middle.block, %.lr.ph95
  %48 = shl i32 %17, 1
  %49 = sext i32 %48 to i64
  %50 = getelementptr inbounds [40021 x i8], ptr @buf, i64 0, i64 %49
  store i8 0, ptr %50, align 2, !tbaa !11
  %51 = add i32 %48, -2
  %.not6278 = icmp slt i32 %51, 0
  br i1 %.not6278, label %._crit_edge84, label %.lr.ph83

.lr.ph:                                           ; preds = %.lr.ph.prol.loopexit, %.lr.ph
  %indvars.iv99 = phi i64 [ %indvars.iv.next100.1, %.lr.ph ], [ %indvars.iv99.unr, %.lr.ph.prol.loopexit ]
  %52 = getelementptr inbounds [20010 x i8], ptr @str, i64 0, i64 %indvars.iv99
  %53 = load i8, ptr %52, align 1, !tbaa !11
  %sext = shl i64 %indvars.iv99, 33
  %54 = ashr exact i64 %sext, 32
  %55 = getelementptr inbounds [40021 x i8], ptr @buf, i64 0, i64 %54
  store i8 %53, ptr %55, align 2, !tbaa !11
  %indvars.iv99.tr = trunc i64 %indvars.iv99 to i32
  %56 = shl i32 %indvars.iv99.tr, 1
  %57 = or disjoint i32 %56, 1
  %58 = sext i32 %57 to i64
  %59 = getelementptr inbounds [40021 x i8], ptr @buf, i64 0, i64 %58
  store i8 35, ptr %59, align 1, !tbaa !11
  %indvars.iv.next100 = add nuw nsw i64 %indvars.iv99, 1
  %60 = getelementptr inbounds [20010 x i8], ptr @str, i64 0, i64 %indvars.iv.next100
  %61 = load i8, ptr %60, align 1, !tbaa !11
  %sext.1 = shl i64 %indvars.iv.next100, 33
  %62 = ashr exact i64 %sext.1, 32
  %63 = getelementptr inbounds [40021 x i8], ptr @buf, i64 0, i64 %62
  store i8 %61, ptr %63, align 2, !tbaa !11
  %indvars.iv99.tr.1 = trunc i64 %indvars.iv.next100 to i32
  %64 = shl i32 %indvars.iv99.tr.1, 1
  %65 = or disjoint i32 %64, 1
  %66 = sext i32 %65 to i64
  %67 = getelementptr inbounds [40021 x i8], ptr @buf, i64 0, i64 %66
  store i8 35, ptr %67, align 1, !tbaa !11
  %indvars.iv.next100.1 = add nuw nsw i64 %indvars.iv99, 2
  %exitcond102.not.1 = icmp eq i64 %indvars.iv.next100.1, %wide.trip.count
  br i1 %exitcond102.not.1, label %._crit_edge, label %.lr.ph, !llvm.loop !15

._crit_edge84:                                    ; preds = %.critedge, %._crit_edge
  call void @_ZN6Bitset4initEi(ptr noundef nonnull align 8 dereferenceable(2520) @f, i32 noundef 1)
  call void @_ZN6Bitset3setEm(ptr noundef nonnull align 8 dereferenceable(2520) @f, i64 noundef 0)
  %68 = load i32, ptr @n, align 4, !tbaa !5
  call void @_ZN6Bitset4initEi(ptr noundef nonnull align 8 dereferenceable(2520) @g, i32 noundef %68)
  %69 = load i32, ptr @n, align 4, !tbaa !5
  %70 = icmp sgt i32 %69, 0
  br i1 %70, label %.lr.ph87, label %.preheader

.lr.ph83:                                         ; preds = %._crit_edge, %.critedge
  %indvars.iv108 = phi i64 [ %indvars.iv.next109, %.critedge ], [ 0, %._crit_edge ]
  %indvars.iv105 = phi i32 [ %indvars.iv.next106, %.critedge ], [ 1, %._crit_edge ]
  %.05381 = phi i32 [ %spec.select68, %.critedge ], [ 0, %._crit_edge ]
  %.05480 = phi i32 [ %spec.select, %.critedge ], [ 0, %._crit_edge ]
  %71 = sext i32 %.05480 to i64
  %72 = icmp slt i64 %indvars.iv108, %71
  call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %1) #10
  br i1 %72, label %73, label %82

73:                                               ; preds = %.lr.ph83
  %74 = trunc nuw nsw i64 %indvars.iv108 to i32
  %75 = sub nsw i32 %.05480, %74
  store i32 %75, ptr %1, align 4, !tbaa !5
  %76 = shl i32 %.05381, 1
  %77 = sext i32 %76 to i64
  %78 = sub nsw i64 %77, %indvars.iv108
  %79 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %78
  %80 = call noundef nonnull align 4 dereferenceable(4) ptr @_ZSt3minIiERKT_S2_S2_(ptr noundef nonnull align 4 dereferenceable(4) %1, ptr noundef nonnull align 4 dereferenceable(4) %79)
  %81 = load i32, ptr %80, align 4, !tbaa !5
  br label %82

82:                                               ; preds = %.lr.ph83, %73
  %83 = phi i32 [ %81, %73 ], [ 0, %.lr.ph83 ]
  %84 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %indvars.iv108
  store i32 %83, ptr %84, align 4, !tbaa !5
  call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %1) #10
  %85 = sext i32 %83 to i64
  %.not6673 = icmp slt i64 %indvars.iv108, %85
  br i1 %.not6673, label %.critedge, label %.lr.ph75

.lr.ph75:                                         ; preds = %82, %93
  %indvars.iv103 = phi i64 [ %indvars.iv.next104, %93 ], [ %85, %82 ]
  %86 = sub nsw i64 %indvars.iv108, %indvars.iv103
  %87 = getelementptr inbounds [40021 x i8], ptr @buf, i64 0, i64 %86
  %88 = load i8, ptr %87, align 1, !tbaa !11
  %89 = add nsw i64 %indvars.iv103, %indvars.iv108
  %90 = getelementptr inbounds [40021 x i8], ptr @buf, i64 0, i64 %89
  %91 = load i8, ptr %90, align 1, !tbaa !11
  %92 = icmp eq i8 %88, %91
  br i1 %92, label %93, label %.critedge.loopexit.split.loop.exit121

93:                                               ; preds = %.lr.ph75
  %indvars.iv.next104 = add nsw i64 %indvars.iv103, 1
  %94 = trunc nsw i64 %indvars.iv.next104 to i32
  store i32 %94, ptr %84, align 4, !tbaa !5
  %.not66.not = icmp slt i64 %indvars.iv103, %indvars.iv108
  br i1 %.not66.not, label %.lr.ph75, label %.critedge, !llvm.loop !16

.critedge.loopexit.split.loop.exit121:            ; preds = %.lr.ph75
  %95 = trunc nsw i64 %indvars.iv103 to i32
  br label %.critedge

.critedge:                                        ; preds = %93, %.critedge.loopexit.split.loop.exit121, %82
  %.lcssa = phi i32 [ %83, %82 ], [ %95, %.critedge.loopexit.split.loop.exit121 ], [ %indvars.iv105, %93 ]
  %96 = trunc nuw nsw i64 %indvars.iv108 to i32
  %97 = add nsw i32 %.lcssa, %96
  %98 = icmp slt i32 %.05480, %97
  %spec.select = call i32 @llvm.smax.i32(i32 %.05480, i32 %97)
  %spec.select68 = select i1 %98, i32 %96, i32 %.05381
  %indvars.iv.next109 = add nuw nsw i64 %indvars.iv108, 1
  %99 = load i32, ptr @n, align 4, !tbaa !5
  %100 = shl i32 %99, 1
  %101 = add i32 %100, -2
  %102 = sext i32 %101 to i64
  %.not62.not = icmp slt i64 %indvars.iv108, %102
  %indvars.iv.next106 = add nuw i32 %indvars.iv105, 1
  br i1 %.not62.not, label %.lr.ph83, label %._crit_edge84, !llvm.loop !17

.preheader:                                       ; preds = %119, %._crit_edge84
  %103 = phi i32 [ %69, %._crit_edge84 ], [ %120, %119 ]
  %104 = shl i32 %103, 1
  %105 = add i32 %104, -2
  %106 = icmp slt i32 %105, 0
  br i1 %106, label %._crit_edge91.thread, label %.lr.ph90

.lr.ph87:                                         ; preds = %._crit_edge84, %119
  %107 = phi i32 [ %120, %119 ], [ %69, %._crit_edge84 ]
  %indvars.iv111 = phi i64 [ %indvars.iv.next112, %119 ], [ 0, %._crit_edge84 ]
  %108 = trunc i64 %indvars.iv111 to i32
  %109 = add i32 %108, -1
  %110 = add i32 %109, %107
  %111 = sext i32 %110 to i64
  %112 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %111
  %113 = load i32, ptr %112, align 4, !tbaa !5
  %114 = trunc nuw nsw i64 %indvars.iv111 to i32
  %115 = xor i32 %114, -1
  %116 = add i32 %107, %115
  %117 = icmp sgt i32 %113, %116
  br i1 %117, label %118, label %119

118:                                              ; preds = %.lr.ph87
  call void @_ZN6Bitset3setEm(ptr noundef nonnull align 8 dereferenceable(2520) @g, i64 noundef %indvars.iv111)
  %.pre = load i32, ptr @n, align 4, !tbaa !5
  br label %119

119:                                              ; preds = %.lr.ph87, %118
  %120 = phi i32 [ %107, %.lr.ph87 ], [ %.pre, %118 ]
  %indvars.iv.next112 = add nuw nsw i64 %indvars.iv111, 1
  %121 = sext i32 %120 to i64
  %122 = icmp slt i64 %indvars.iv.next112, %121
  br i1 %122, label %.lr.ph87, label %.preheader, !llvm.loop !18

._crit_edge91:                                    ; preds = %148
  %spec.select123 = select i1 %138, ptr @.str.2, ptr @.str.3
  br label %._crit_edge91.thread

._crit_edge91.thread:                             ; preds = %._crit_edge91, %.preheader
  %123 = phi ptr [ @.str.3, %.preheader ], [ %spec.select123, %._crit_edge91 ]
  %124 = call i32 @puts(ptr noundef nonnull dereferenceable(1) %123)
  %125 = load i32, ptr @t, align 4, !tbaa !5
  %126 = add nsw i32 %125, -1
  store i32 %126, ptr @t, align 4, !tbaa !5
  %.not = icmp eq i32 %125, 0
  br i1 %.not, label %._crit_edge96, label %.lr.ph95, !llvm.loop !19

.lr.ph90:                                         ; preds = %.preheader, %148
  %indvars.iv114 = phi i64 [ %.pre116, %148 ], [ 0, %.preheader ]
  %127 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %indvars.iv114
  %128 = load i32, ptr %127, align 4, !tbaa !5
  %129 = trunc nuw nsw i64 %indvars.iv114 to i32
  %130 = and i32 %129, 1
  %131 = xor i32 %129, -1
  %132 = add i32 %128, %131
  %133 = and i32 %132, 1
  %134 = add nuw nsw i32 %130, %133
  %135 = sub i32 %128, %134
  %.fr124 = freeze i32 %135
  %136 = ashr i32 %.fr124, 1
  call void @llvm.lifetime.start.p0(i64 2520, ptr nonnull %2) #10
  call void @_ZNK6BitsetanERKS_(ptr dead_on_unwind nonnull writable sret(%struct.Bitset) align 8 %2, ptr noundef nonnull align 8 dereferenceable(2520) @f, ptr noundef nonnull align 8 dereferenceable(2520) @g)
  call void @llvm.memcpy.p0.p0.i64(ptr noundef nonnull align 8 dereferenceable(2520) @w, ptr noundef nonnull align 8 dereferenceable(2520) %2, i64 2520, i1 false), !tbaa.struct !20
  call void @llvm.lifetime.end.p0(i64 2520, ptr nonnull %2) #10
  call void @_ZN6Bitset15shift_right_oneEv(ptr noundef nonnull align 8 dereferenceable(2520) @w)
  %137 = call noundef i32 @_ZNK6Bitset6lowbitEv(ptr noundef nonnull align 8 dereferenceable(2520) @w)
  %138 = icmp sle i32 %137, %136
  %.not65 = icmp eq i32 %130, 0
  %.pre116 = add nuw nsw i64 %indvars.iv114, 1
  br i1 %.not65, label %147, label %139

139:                                              ; preds = %.lr.ph90
  call void @_ZN6Bitset14shift_left_oneEv(ptr noundef nonnull align 8 dereferenceable(2520) @f)
  %140 = trunc nuw nsw i64 %.pre116 to i32
  %141 = lshr exact i32 %140, 1
  %142 = zext nneg i32 %141 to i64
  %143 = getelementptr inbounds [40020 x i32], ptr @h, i64 0, i64 %142
  %144 = load i32, ptr %143, align 4, !tbaa !5
  %145 = icmp sgt i32 %144, %141
  br i1 %145, label %146, label %148

146:                                              ; preds = %139
  call void @_ZN6Bitset3setEm(ptr noundef nonnull align 8 dereferenceable(2520) @f, i64 noundef 0)
  br label %148

147:                                              ; preds = %.lr.ph90
  call void @_ZN6Bitset15shift_right_oneEv(ptr noundef nonnull align 8 dereferenceable(2520) @g)
  br label %148

148:                                              ; preds = %139, %146, %147
  %149 = load i32, ptr @n, align 4, !tbaa !5
  %150 = shl i32 %149, 1
  %151 = add i32 %150, -2
  %152 = sext i32 %151 to i64
  %153 = icmp sge i64 %indvars.iv114, %152
  %.not64 = or i1 %153, %138
  br i1 %.not64, label %._crit_edge91, label %.lr.ph90, !llvm.loop !23

._crit_edge96:                                    ; preds = %._crit_edge91.thread, %3
  ret i32 0
}

; Function Attrs: mustprogress nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.start.p0(i64 immarg, ptr nocapture) #1

; Function Attrs: mustprogress nocallback nofree nosync nounwind willreturn memory(argmem: readwrite)
declare void @llvm.lifetime.end.p0(i64 immarg, ptr nocapture) #1

; Function Attrs: nofree nounwind
declare noundef i32 @__isoc99_scanf(ptr nocapture noundef readonly, ...) local_unnamed_addr #2

; Function Attrs: mustprogress nofree nounwind willreturn memory(argmem: read)
declare i64 @strlen(ptr nocapture noundef) local_unnamed_addr #3

; Function Attrs: inlinehint mustprogress nounwind uwtable
declare dso_local noundef nonnull align 4 dereferenceable(4) ptr @_ZSt3minIiERKT_S2_S2_(ptr noundef nonnull align 4 dereferenceable(4), ptr noundef nonnull align 4 dereferenceable(4)) local_unnamed_addr #4

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZN6Bitset4initEi(ptr noundef nonnull align 8 dereferenceable(2520), i32 noundef) local_unnamed_addr #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZN6Bitset3setEm(ptr noundef nonnull align 8 dereferenceable(2520), i64 noundef) local_unnamed_addr #5 align 2

; Function Attrs: mustprogress uwtable
declare dso_local void @_ZNK6BitsetanERKS_(ptr dead_on_unwind noalias writable sret(%struct.Bitset) align 8, ptr noundef nonnull align 8 dereferenceable(2520), ptr noundef nonnull align 8 dereferenceable(2520)) local_unnamed_addr #6 align 2

; Function Attrs: mustprogress nocallback nofree nounwind willreturn memory(argmem: readwrite)
declare void @llvm.memcpy.p0.p0.i64(ptr noalias nocapture writeonly, ptr noalias nocapture readonly, i64, i1 immarg) #7

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZN6Bitset15shift_right_oneEv(ptr noundef nonnull align 8 dereferenceable(2520)) local_unnamed_addr #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local noundef i32 @_ZNK6Bitset6lowbitEv(ptr noundef nonnull align 8 dereferenceable(2520)) local_unnamed_addr #5 align 2

; Function Attrs: mustprogress nounwind uwtable
declare dso_local void @_ZN6Bitset14shift_left_oneEv(ptr noundef nonnull align 8 dereferenceable(2520)) local_unnamed_addr #5 align 2

; Function Attrs: nofree nounwind
declare noundef i32 @puts(ptr nocapture noundef readonly) local_unnamed_addr #2

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i32 @llvm.smax.i32(i32, i32) #8

attributes #0 = { mustprogress norecurse uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { mustprogress nocallback nofree nosync nounwind willreturn memory(argmem: readwrite) }
attributes #2 = { nofree nounwind "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #3 = { mustprogress nofree nounwind willreturn memory(argmem: read) "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #4 = { inlinehint mustprogress nounwind uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #5 = { mustprogress nounwind uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #6 = { mustprogress uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #7 = { mustprogress nocallback nofree nounwind willreturn memory(argmem: readwrite) }
attributes #8 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }
attributes #9 = { nounwind willreturn memory(read) }
attributes #10 = { nounwind }

!llvm.module.flags = !{!0, !1, !2, !3}
!llvm.ident = !{!4}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{!"clang version 19.1.0 (git@github.com:llvm/llvm-project.git a4bf6cd7cfb1a1421ba92bca9d017b49936c55e4)"}
!5 = !{!6, !6, i64 0}
!6 = !{!"int", !7, i64 0}
!7 = !{!"omnipotent char", !8, i64 0}
!8 = !{!"Simple C++ TBAA"}
!9 = distinct !{!9, !10}
!10 = !{!"llvm.loop.mustprogress"}
!11 = !{!7, !7, i64 0}
!12 = distinct !{!12, !10, !13, !14}
!13 = !{!"llvm.loop.isvectorized", i32 1}
!14 = !{!"llvm.loop.unroll.runtime.disable"}
!15 = distinct !{!15, !10, !13}
!16 = distinct !{!16, !10}
!17 = distinct !{!17, !10}
!18 = distinct !{!18, !10}
!19 = distinct !{!19, !10}
!20 = !{i64 0, i64 4, !5, i64 8, i64 8, !21, i64 16, i64 2504, !11}
!21 = !{!22, !22, i64 0}
!22 = !{!"long", !7, i64 0}
!23 = distinct !{!23, !10}


; Effective O3 passes: CorrelatedValuePropagationPass,EarlyCSEPass,GVNPass,GlobalDCEPass,GlobalOptPass,IPSCCPPass,IndVarSimplifyPass,InferAlignmentPass,InferFunctionAttrsPass,InstCombinePass,InstSimplifyPass,JumpThreadingPass,LCSSAPass,LICMPass,LoopLoadEliminationPass,LoopRotatePass,LoopSimplifyPass,LoopUnrollPass,LoopVectorizePass,ReassociatePass,SROAPass,SimplifyCFGPass,TailCallElimPass